最大子矩阵

类似于面试题17.24;

不过是每个单元的元素只是一,可以把问题转化为求取面积。

直接用单调栈求取从一个柱子可扩展的的最大面积即可。

代码

#include <iostream>
#include <vector>
#include <map>
#include <stack>
using namespace std;
int n , m;
vector<int> height;
int maxarea = 0;

void caculateArea(vector<int>&area){
    for(int i = 0; i < area.size(); ++i){
        if(area[i]) height[i] += area[i];
        else height[i] = 0;

    }
    stack<int> st;
    height.push_back(0);
    
    for(int i = 0; i < height.size(); ++i){

        while(st.size() && height[st.top()] >= height[i]){
            int hei = height[st.top()];
            st.pop();
            int l = st.size() ? st.top() : -1;
            maxarea = max(maxarea, (i - 1 - l)* hei);
          //  cout << l << ' ' << maxarea << ' ' << i - 1  << ' ' << hei<< endl;

        }
        st.push(i);
    }
    height.erase(height.end() - 1);
    
}


int main(){
    cin >> n  >> m;
    vector<int> maze(m);
    height.resize(m);
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < m; ++j) cin >> maze[j];
        caculateArea(maze);
    }
    cout << maxarea << endl;
    return 0;
}

84. Largest Rectangle in Histogram

84. Largest Rectangle in Histogram

思路:

  1. 遍历高度数组的同时,维护形成的矩阵,并更新最大面积。
  2. 观察,矩阵的面积可以不严格递增的情况下在从左到右扩展的,再严格递减的情况下可以确定出矩阵面积。正向数据缓存,逆向面积计算-> 单调栈。read more

代码:

class Solution {
    map<int, pair<int,int>> reg;
public:
    int largestRectangleArea(vector<int>& heights) {
        int maxarea = 0;
        for(int i = 0; i < heights.size(); ++i){
            
            for(auto &item : reg){
                auto high = item.first; 
                auto &pii = item.second;
                auto l = pii.first;
                auto &r = pii.second;
                if(high > heights[i]){
                    reg.insert({heights[i], {l, i}});
                    maxarea = max(maxarea, heights[i] *(i - l + 1));
                    reg.erase(reg.find(high), reg.end());
                    
                    break;
                } 
                else if(high <= heights[i]){
                    r = i;
                    maxarea = max(high * (r - l + 1), maxarea);
                }
            }
            if(reg.count(heights[i]) == 0){
                reg.insert({heights[i], {i, i}});
                maxarea = max(maxarea, heights[i]);
            }
        }
        return maxarea;
    }
};
class Solution {
    stack<int> s;
public:
    int largestRectangleArea(vector<int>& heights) {
        int maxarea = 0;
        heights.push_back(0); // 为了计算所有面积
        for(int i = 0; i < heights.size(); ++i){
            if(s.empty()) s.push(i);
            else if(heights[s.top()] < heights[i]) s.push(i);
            else if(heights[s.top()] == heights[i]) s.top() = i; // 如果相邻的高度相同,则更新;因为不更新单调栈中矩阵左边界会扩展更多
            else if(heights[s.top()] > heights[i]){         
                while(!s.empty() && (heights[s.top()] > heights[i])){                    
                    int high = heights[s.top()]; 
                    s.pop();
                    int temparea = ( i - (s.empty() ? -1 : s.top()) - 1) * high;
                    maxarea = max(maxarea, temparea);
                }
                s.push(i);   
            }   
        }
        return maxarea;
    }
};

当然,这里也可以添加一个哨兵,不过没什么影响。

32. Longest Valid Parentheses

思路:

栈验证匹配括号很简单,但是用如何获取多个匹配成功的括号组合长度就很麻烦!

难的是想到,连续的有效括号()())()()只需要记录一个最先未匹配的位置。具体做法是,在栈中存储一个最后没有匹配到的右括号下标。

代码

class Solution {
public:
    int longestValidParentheses(string s) {
        int maxlen = 0; 
        stack<int> st;
        
        st.push(-1); // 压入一个最后未匹配的)。
        for(int i = 0; i < s.size(); ++i){
            if(s[i] == ')'){
                st.pop();
                if(!st.empty()){ // 刚刚的)匹配成功,可以计算最长匹配
                    maxlen = max(maxlen, i - st.top()); 
                }else st.push(i); // 说明该)没有匹配到,是新的最后的最右括号
            }else st.push(i);
        }
        return maxlen;
    }
};

42. Trapping Rain Water

42. Trapping Rain Water

思路:

这题蛮hard的,挺考验思路;

思考一下,下雨的过程,水往低处流,一点一点汇聚起来,逐渐逐渐升高水面。我们是否可以在先求出低水平面的水量,在此之上求出高水平面的水量。

43234中就有两个水沟:2上的1*1的水沟,和323上的3*1水沟。

用这种想法,我们只需要遍历得到一个水平面的右边界,记录该水平面的左边界,获取低水平面的高度,填充下新水平面的水量即可。

最小值单调栈S可以帮助我们维持左边界的pos,记S的栈顶元素指向的高度为aa之下的元素指向的高度为b。其性质必然有a > b。遍历到高度c

  • c < a,则对蓄水没有影响。
  • 如果c > b,则三者形成了一个水沟,计算🦁式子见代码,并且该水沟可能可以继续往上“看看”,在适当条件上看看单调栈,循环填充高水位水沟。
  • 如果c==a,则显然应该替换掉a,因为单调栈维持的是等高水沟的最新端,试想33323

经过上述填充过程,单调栈的性质也要维护一下,详细见代码。

Read more

155. Min Stack

155. Min Stack

思路:

用另一个栈保存另一个栈的各个元素插入,删除后的最小值。

他利用这么一个现象:后插入的大元素不会影响这个栈的最小值,反之小元素会改变。那么只要把此时小元素插入到最小栈即可,同理删除元素的时候也按值删除。

Read more

739. Daily Temperatures

739. Daily Temperatures

思路:

  1. 单调栈;用单调栈维护从后往前遍历当前元素的最大值,便可以轻松获取当前元素之后的最大值下标,即可以更新下一个更大元素的时间差。

  2. KMP失败匹配算法;从后往前遍历,当前元素的更大值要么是当前元素的下一个元素,要么是下一个元素的更大值,要么是下一个元素的更大值的更大值……如此“递归”查找可得下一个最大值。如果查找不到,就不存在最大值。

Read more