（leetcode算法题）84. 柱状图中最大的矩形 2334. 元素值大于变化阈值的子数组

将这个问题进行转化，就能变成典型的单调栈的问题，

由于原问题中矩形的面积完全取决于其中最小矩形的高度，那么很容易想到遍历每个矩形，让每一个矩形都做一次最小矩形，看看其能够覆盖的最大宽度是多少，就能找到题目的答案。

进一步，对于第 i 号能够形成的矩形来说，我们可以将其分为两部分看待，其高度都是heights[i],

矩形的左半部分：宽度是从 i 开始往回数，大于或等于heights[i] 的最大连续的区间长度

矩形的右半部分：宽度是从 i 开始往后数，大于或等于heights[i] 的最大连续的区间长度

是不是想到901. 股票价格跨度 当时的情况了呢？但是与901不同的是，需要考虑从左遍历和从右遍历的两种情况进行相加

那么901使用了一个从栈底到栈顶单调递减栈作为辅助容器，帮助获得小于等于当前位置的连续区间长度，这里自然可以使用一个从栈底到栈顶单调递增栈作为辅助容器，帮助获得大于等于当前位置的连续区间长度

但是！！！！！！！！！！！！！！！！！！！！！！！！！！

这里需要注意更新矩形左右半部分的长度策略，我们以左半部分为例

由于采取了单调递增栈，那么当遍历到heights[i] 这个高度时，我们想要更新的到底是什么，策略有两种

策略一：找到大于等于heights[i] 的且离 i  最远的  那个下标，那么这个就是左半部分的端点

策略二：找到小于 heights[i]  的且离 i 最近的 那个下标，加一就是左半部分的端点

如果将每更新一个端点就去遍历的方案视为错，那么这两种策略一对一错，读者不妨考虑一下哪个是对的？

~

~

~

~

公布答案，策略二是对的！

策略一的反例，对于 heights = [3,6,5,7,4,8,1,0] 来说，在更新 heights[i] = 4 这个点的左半部分的端点时，如果想用单调递增栈找到 6，这是不可能的，因为在更新heights[i] = 5 时，这个已经把6pop出栈，此时要妄想使用记录6下标的逻辑的话，就是一个暴力遍历的过程，所以此时采用策略二：

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        stack<int> st;
        vector<int> recordleft(n, -1);
        vector<int> recordright(n, n);
        for(int i = 0; i < n; ++i){
/*利用从栈底到栈顶的单调递增栈更新*/
/*记录当前木板离他最近的那个小于当前木板高度的下标*/
            while(!st.empty() && heights[st.top()] >= heights[i]){
                st.pop();
            }
            if(!st.empty()){
                recordleft[i] = st.top();
            }
            st.push(i);
        }
        st = stack<int> ();
        for(int j = n - 1; j >= 0; --j){
            while(!st.empty() && heights[st.top()] >= heights[j]){
                st.pop();
            }
            if(!st.empty()){
                recordright[j] = st.top();
            }
            st.push(j);           
        }
        int ret = 0;
        for(int i = 0; i < n; ++i){
            int curlongestlen = recordright[i] - recordleft[i] - 1;
            ret = max(ret, curlongestlen * heights[i]);
        }
        return ret;
    }
};

这里可以采用与84题相同的算法来更新，这是因为2334也可以转换成一个相同的问题：将nums[i]作为连续子数组中最小的那个数，更新出连续子数组的的长度 k，然后判断 nums[i] / k 和threshold的关系

那么这个题和 84不是一模一样的两个题吗！！！

class Solution {
public:
    int validSubarraySize(vector<int>& nums, int threshold) {
        int n = nums.size();
        stack<int> st;
        // vector<int> biggestminsubnumthancurnuminleft(n);
        vector<int> bmsntcinl(n);
        for(int i = 0; i < n; ++i){
            while(!st.empty() && nums[st.top()] >= nums[i]){
                st.pop();
            }
            if(!st.empty()){
                bmsntcinl[i] = st.top();
            }
            else{
                bmsntcinl[i] = -1;
            }
            st.push(i);
        }
        st = stack<int> ();
        // vector<int> biggestminsubnumthancurnuminright(n);
        vector<int> bmsntcinr(n);
        for(int j = n - 1; j >= 0; --j){
            while(!st.empty() && nums[st.top()] >= nums[j]){
                st.pop();
            }
            if(!st.empty()){
                bmsntcinr[j] = st.top();
            }
            else{
                bmsntcinr[j] = n;
            }
            st.push(j);
        }

        for(int i = 0; i < n; ++i){
            int curk = bmsntcinr[i] - bmsntcinl[i] - 1;
            // 在nums的从bmsntcinr[i] + 1 到 bmsntcinl[i] - 1的这些位置中
            // 所有数都比nums[i]大
            if(nums[i] > threshold / curk){
                return curk;
            }
        }
        return -1;
    }
};

原文地址：https://blog.csdn.net/weixin_46366676/article/details/145225669

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！