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;
    }
};

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

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

739. Daily Temperatures

739. Daily Temperatures

思路:

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

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

Read more