JLUVicent

42接雨水&503下一个更大元素II

 
  • 2023年 04月14日
  • 0 阅读

day59

503.下一个更大元素II

题目链接：503. 下一个更大元素 II

解题思路：参考 视频

参考之前的每日温度，不同的是该数组为环形数组，要解决该问题，有两种方法

第一种：复制数组变成两个

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

第二种，用取模来进行成环遍历

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

    }
};

42.接雨水

题目链接：42. 接雨水

解题思路：参考 视频

有以下三种方法

暴力解法

首先明确按行计算还是按列计算

按行：

42.接雨水2

按列

42.接雨水1

按列来计算的话，宽度一定为1，将每一列的高度计算出来即可，

第一个柱子和最后一个柱子不接雨水

		//时间 O(n^2)
		//空间 O(1)
		int sum = 0;
        for( int i = 0; i < height.size(); i++){
            if( i == 0 || i == height.size()-1) continue;   //第一个和最后一个不接雨水
            int rHeight = height[i];
            int lHeight = height[i];
            for( int r = i + 1; r < height.size(); r++){
                if( height[r] > rHeight) rHeight = height[r];
            }
            for( int l = i - 1; l >= 0 ; l--){
                if( height[l] > lHeight) lHeight = height[l];
            }
            int h = min(lHeight,rHeight) - height[i];
            if( h > 0) sum+=h;
        }
        return sum;

双指针优化

        // 双指针优化
        vector<int> maxLeft(height.size(),0);	//另外开辟出两个数组，分别记录每个元素右边的最大值和左边的最大值，然后计算每一个的
        vector<int> maxRight(height.size(),0);
        int size = height.size();

        maxLeft[0] = height[0];
        for( int i = 1; i < size; i++){
            maxLeft[i] = max( height[i],maxLeft[i-1]);
        }
        
        maxRight[size-1] = height[size-1];
        for( int i = size-2; i >= 0; i--){
            maxRight[i] = max( height[i],maxRight[i+1]);
        }

        // 求和
        int sum = 0;
        for( int i = 0; i < size; i++){
            int count = min(maxLeft[i],maxRight[i]) - height[i];  //相当于只计算高度
            if( count > 0 ) sum+=count;
        }
        return sum;

单调栈

按行方向来计算雨水，思路参考每日温度，计算出高度和宽度，最后相乘即可。

42.接雨水2

class Solution {
public:
    int trap(vector<int>& height) {
        //单调栈
        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{
                while( !st.empty() && height[i] > height[st.top()]){
                    int mid = st.top();
                    st.pop();
                    if( !st.empty()){
                        int h = min(height[st.top()],height[i]) - height[mid];
                        int w = i - st.top() - 1;
                        sum += h*w;
                    }
                }
                st.push(i);
            }
        }
        return sum;

        // 暴力求解 超时
        // int sum = 0;
        // for( int i = 0; i < height.size(); i++){
        //     if( i == 0 || i == height.size()-1) continue;   //第一个和最后一个不接雨水
        //     int rHeight = height[i];
        //     int lHeight = height[i];
        //     for( int r = i + 1; r < height.size(); r++){
        //         if( height[r] > rHeight) rHeight = height[r];
        //     }
        //     for( int l = i - 1; l >= 0 ; l--){
        //         if( height[l] > lHeight) lHeight = height[l];
        //     }
        //     int h = min(lHeight,rHeight) - height[i];
        //     if( h > 0) sum+=h;
        // }
        // return sum;

        // 双指针优化
        // vector<int> maxLeft(height.size(),0);
        // vector<int> maxRight(height.size(),0);
        // int size = height.size();

        // maxLeft[0] = height[0];
        // for( int i = 1; i < size; i++){
        //     maxLeft[i] = max( height[i],maxLeft[i-1]);
        // }
        
        // maxRight[size-1] = height[size-1];
        // for( int i = size-2; i >= 0; i--){
        //     maxRight[i] = max( height[i],maxRight[i+1]);
        // }

        // // 求和
        // int sum = 0;
        // for( int i = 0; i < size; i++){
        //     int count = min(maxLeft[i],maxRight[i]) - height[i];  //相当于只计算高度
        //     if( count > 0 ) sum+=count;
        // }
        // return sum;

    }
};
搜索