C++ day59 下一个更大元素Ⅱ 接雨水

题目1：503 下一个更大元素Ⅰ

题目链接：下一个更大元素Ⅱ

对题目的理解

返回循环数组中每个元素的下一个更大元素，

数字x的下一个更大元素是循环等的搜索它的最近的下一个更大的数

数组的中至少有一个元素

本题难点在于循环遍历这里，环形数组

法一：合并拼接两个数组

代码

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        vector<int> nums1(nums.begin(),nums.end());
        nums.insert(nums.end(),nums1.begin(),nums1.end());
        vector<int> result(nums.size(),-1);
        stack<int> st;
        st.push(0);
        for(int i=1;i<nums.size();i++){
            if(nums[i]<nums[st.top()]) st.push(i);
            else if(nums[i]==nums[st.top()]) st.push(i);
            else {
                while(!st.empty() && nums[i]>nums[st.top()]){
                    result[st.top()]=nums[i];
                    st.pop();
                }
                st.push(i);
            }
        }
        result.resize(nums.size()/2);
        //result.resize(nums1.size());//这句代码与上一句的作用相同
        return result;
    }
};

精简代码

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        vector<int> nums1(nums.begin(),nums.end());
        nums.insert(nums.end(),nums1.begin(),nums1.end());
        vector<int> result(nums.size(),-1);
        stack<int> st;
        st.push(0);
        for(int i=1;i<nums.size();i++){
            while(!st.empty() && nums[i]>nums[st.top()]){
                result[st.top()]=nums[i];
                st.pop();
            }
            st.push(i);
        }
        result.resize(nums.size()/2);
        //result.resize(nums1.size());//这句代码与上一句的作用相同
        return result;
    }
};

这种写法确实比较直观，但做了很多无用操作，例如修改了nums数组，而且最后还要把result数组resize回去，resize倒是不费时间，是O(1)的操作，但扩充nums数组相当于多了一个O(n)的操作。

法二：取模的方式进行循环成环问题的求解

不扩充nums，而是在遍历的过程中模拟走了两边nums，这就是利用取模的方式解决这种循环的问题

伪代码

代码

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        vector<int> result(nums.size(),-1);
        stack<int> st;
        st.push(0);//在栈中放入第一个元素的下标
        for(int i=1;i<2*nums.size();i++){
            if(nums[i%nums.size()]<nums[st.top()]) st.push(i%nums.size());
            else if(nums[i%nums.size()]==nums[st.top()]) st.push(i%nums.size());
            else {
                while(!st.empty() && nums[i%nums.size()]>nums[st.top()]){
                    result[st.top()]=nums[i%nums.size()];
                    st.pop();
                }
                st.push(i%nums.size());
            }    
        }
        return result;
    }
};

精简代码

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        vector<int> result(nums.size(),-1);
        stack<int> st;
        for(int i=0;i<2*nums.size();i++){
            while(!st.empty() && nums[i%nums.size()]>nums[st.top()]){
                result[st.top()]=nums[i%nums.size()];
                st.pop();
            }
            st.push(i%nums.size());
        }
        return result;
    }
};

代码流程

题目2：42 接雨水

题目链接：接雨水

对题目的理解

是面试高频题，是单调栈应用的题目，掌握双指针（更直接）和单调栈（有难度）的方法

暴力解法（纵向求解，按列计算）

按照列计算，宽度是定值1，把每一列的雨水高度求出来就可。

每列雨水的高度取决于该列左侧最高的柱子和右侧最高的柱子的值最小的那个柱子的高度，for循环中求左右两边最高柱子，取最小值

从头遍历一遍所有的列，然后求出每一列雨水的面积，相加之后就是总雨水的面积了，注意第一个柱子和最后一个柱子不接雨水

代码1

class Solution {
public:
    int trap(vector<int>& height) {
        //遍历整个列，求出每列雨水的高度，高度*宽度（1）=面积，再加和就是总面积
        int sum = 0;
        for(int i=0;i<height.size();i++){
            if(i==0 || i==height.size()-1) continue;
            int right_height = 0;
            for(int r=i+1;r<height.size();r++){//当前列雨水右边的高度
                //当前列雨水右边的高度大于当前列雨水的高度
                if(height[r]>height[i]) right_height = max(right_height,height[r]);
            }
            int left_height = 0;
            for(int l=i-1;l>=0;l--){//当前列雨水左边的高度
                //当前列雨水左边的高度大于当前列雨水的高度
                if(height[l]>height[i]) left_height = max(left_height,height[l]);
            }
            int h = min(left_height,right_height)-height[i];//凹槽雨水的高度
            if(h>0) sum += h;//注意只有h大于0的时候，才做加和，
            //可能会出现高度一直递减的情况，右边高度和左边高度一直为0，那么求得的差值就小于0
        }
        return sum;
    }
};

代码2

class Solution {
public:
    int trap(vector<int>& height) {
        //遍历整个列，求出每列雨水的高度，高度*宽度（1）=面积，再加和就是总面积
        int sum = 0;
        for(int i=0;i<height.size();i++){
            if(i==0 || i==height.size()-1) continue;
            int right_height = height[i];
            for(int r=i+1;r<height.size();r++){//当前列雨水右边的高度
                //当前列雨水右边的高度大于当前列雨水的高度
                if(height[r]>right_height) right_height = height[r];
            }
            int left_height = height[i];
            for(int l=i-1;l>=0;l--){//当前列雨水左边的高度
                //当前列雨水左边的高度大于当前列雨水的高度
                if(height[l]>left_height) left_height = height[l];
            }
            int h = min(left_height,right_height)-height[i];//凹槽雨水的高度
            if(h>0) sum += h;//注意只有h大于0的时候，才做加和，
            //可能会出现高度一直递减的情况，右边高度和左边高度一直为0，那么求得的差值就小于0
        }
        return sum;
    }
};

每次遍历列的时候，还要向两边寻找最高的列，时间复杂度为O(n^2)，空间复杂度为O(1)。

上述两段代码会超时

双指针

暴力解法中为了得到两边的最高高度，使用双指针遍历，每到一个柱子都向两边遍历一遍，这其实是有重复计算的。我们把每一个位置的左边最高高度记录在一个数组上（maxLeft），右边最高高度记录在一个数组上（maxRight），这样就避免了重复计算。

当前位置，左边的最高高度是前一个位置的左边最高高和本高度的最大值

代码

class Solution {
public:
    int trap(vector<int>& height) {
        if(height.size()<=2) return 0;
        vector<int> maxleft(height.size(),0);
        vector<int> maxright(height.size(),0);
        //每个柱子左边柱子的最大高度
        maxleft[0] = height[0];
        for(int i=1;i<height.size();i++){
            maxleft[i]=max(height[i],maxleft[i-1]);
        }
        //每个柱子右边柱子的最大高度
        maxright[height.size()-1]=height[height.size()-1];
        for(int i=height.size()-2;i>=0;i--){
            maxright[i]=max(height[i],maxright[i+1]);
        }
        //求面积和
        int sum=0;
        for(int i=0;i<height.size();i++){
            int h=min(maxleft[i],maxright[i])-height[i];
            if(h>0) sum += h;
        }
        return sum;
    }
};

上述双指针优化过的代码就不会报超时错误了，可以顺利运行

单调栈（横向求解，按行计算）

接雨水这道题目，需要寻找一个元素，右边最大元素以及左边最大元素，来计算雨水面积，因此使用单调栈。

添加的柱子高度大于栈头元素了，此时就出现凹槽了，栈头元素就是凹槽底部的柱子，栈头第二个元素就是凹槽左边的柱子，而添加的元素就是凹槽右边的柱子。

遇到相同的元素，更新栈内下标，就是将栈里元素（旧下标）弹出，将新元素（新下标）加入栈中，求宽度的时候 如果遇到相同高度的柱子，需要使用最右边的柱子来计算宽度。

过 长 * 宽 来计算雨水面积的，长就是通过柱子的高度来计算，宽是通过柱子之间的下标来计算，

栈里就存放下标就行，想要知道对应的高度，通过height[stack.top()] 就知道弹出的下标对应的高度了。

逻辑主要就是三种情况

• 情况一：当前遍历的元素（柱子）高度小于栈顶元素的高度 height[i] < height[st.top()] 当前元素入栈
• 情况二：当前遍历的元素（柱子）高度等于栈顶元素的高度 height[i] == height[st.top()] 栈顶元素弹出，当前元素入栈
• 情况三：当前遍历的元素（柱子）高度大于栈顶元素的高度 height[i] > height[st.top()]? 此时出现凹槽，取栈顶元素，将栈顶元素弹出，这个就是凹槽的底部，也就是中间位置，下标记为mid，对应的高度为height[mid]；此时的栈顶元素st.top()，就是凹槽的左边位置，下标为st.top()，对应的高度为height[st.top()]，当前遍历的元素i，就是凹槽右边的位置，下标为i，对应的高度为height[i]，其实就是栈顶和栈顶的下一个元素以及要入栈的元素，三个元素来接水！雨水高度是 min(凹槽左边高度, 凹槽右边高度) - 凹槽底部高度，雨水的宽度是 凹槽右边的下标 - 凹槽左边的下标 - 1（因为只求中间宽度），当前凹槽雨水的体积就是：高度*宽度

伪代码

代码

class Solution {
public:
    int trap(vector<int>& height) {
        if(height.size()<=2) return 0;//如果数组中至多有两个元素，肯定不能形成凹槽
        int sum = 0;
        stack<int> st;
        st.push(0);
        for(int i=1;i<height.size();i++){
            if(height[i]<height[st.top()]) st.push(i);
            else if(height[i]==height[st.top()]){
                st.pop();
                st.push(i);
            }
            else {
                while(!st.empty() && height[i]>height[st.top()]){
                    int mid = st.top();//记录中间元素
                    st.pop();
                    if(!st.empty()){//前面将top元素弹出，因此判断st是否为空
                        int h = min(height[i],height[st.top()])-height[mid];
                        int w = i-st.top()-1;
                        sum += h*w;
                    }
                }
                st.push(i);
            }
        }
        return sum;
    }
};

精简代码

class Solution {
public:
    int trap(vector<int>& height) {
        if(height.size()<=2) return 0;//如果数组中至多有两个元素，肯定不能形成凹槽
        int sum = 0;
        stack<int> st;
        for(int i=0;i<height.size();i++){
            while(!st.empty() && height[i]>height[st.top()]){
                int mid = st.top();//记录中间元素
                st.pop();
                if(!st.empty()){//前面将top元素弹出，因此判断st是否为空
                    int h = min(height[i],height[st.top()])-height[mid];
                    int w = i-st.top()-1;
                    sum += h*w;
                }
            }
            st.push(i);
        }
        return sum;
    }
};

代码流程