(59/60)下一个更大元素Ⅱ、接雨水

终于接到你

下一个更大元素Ⅱ

leetcode：496. 下一个更大元素 I

单调栈

思路

主要是循环数组的处理。

直接等效为长度为2N，重复两遍的原数组即可，i<nums.size()变为i<2*nums.size()、i变为i%nums.size()。

代码实现

对每个元素都再遍历一遍原数组长度,,,时间复杂度O(N^2)，超时了

class Solution {
public:
/*
走了一圈如果又找到自己了说明自己是最大的，最大的为-1
遍历
*/
    vector<int> nextGreaterElements(vector<int>& nums) {
        vector<int> result(nums.size(),-1); // result存的是下一个更大元素值
        stack<int> st;  // 栈存下标
        st.push(0);
        int curIndex = 0;
        for(int i = 1;i < nums.size();i++){
            int j = i;
            do{
                if(j == nums.size()) j = 0;
                while(!st.empty() && nums[j] > nums[st.top()]){
                    result[st.top()] = nums[j];
                    st.pop();
                }
                st.push(j);
                j++;
            }while(j != i);
        }

        return result;
    }
};

正确的循环数组处理：

class Solution {
/*
循环两倍数组长度就行了
*/
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        vector<int> result(nums.size(),-1); // result存的是下一更大元素值
        stack<int> st;  // st存下标？
        st.push(0);
        for(int i = 1;i < nums.size()*2;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;
    }
};

接雨水

leetcode：42. 接雨水

单调栈

代码实现

class Solution {
public:
/*
单调栈横向求解
自顶向下单调递增栈（找下一个更高柱子）
比较当前 遍历元素 和 栈顶元素
< 入栈
== 先出栈再入栈（去除重复元素避免后续重复计算）
> 进行雨水面积计算（横向）:
    1. 记录当前栈顶为mid；弹出栈顶
    2. h = min(height[i],height[st.top()]) - height[mid];
    3. w = i - st.top() - 1;
    4. sum += h*w;
*/
    int trap(vector<int>& height) {
        stack<int> st; // 存下标
        st.push(0);
        int sum = 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()){
                        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) {
        stack<int> st; // 存下标，自顶向下单调递增
        st.push(0);
        int sum = 0;
        for(int i = 1;i < height.size();i++){
            while(!st.empty() && height[i] > height[st.top()]){
                int mid = st.top(); st.pop();
                if(!st.empty()){
                    int h = min(height[i],height[st.top()]) - height[mid];
                    int w = i - st.top() - 1;
                    sum += h*w;
                }
            }
            st.push(i); // 别忘了 三种情况下最后都要push
        }

        return sum;
    }
};

TS：

/**写个TS版本 */
function trap(height: number[]): number {
    const st:number[] = [];
    st.unshift(0);
    let sum:number = 0;
    for(let i = 1;i < height.length;i++){
        while(st.length !== 0 && height[i] > height[st[0]]){
            const mid:number = st.shift();
            if(st.length !== 0){
                const h:number = Math.min(height[i],height[st[0]]) - height[mid];
                const w:number = i - st[0] - 1;
                sum += h*w;
            }
        }
        st.unshift(i);
    }

    return sum;
};