算法训练营第五十九天|503.下一个更大元素II 42. 接雨水

Leetcode503.下一个更大元素II

思路：相当于把两个数组拼在一起，用 % 操作节省时间复杂度

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 < nums.size() * 2; i++){
            if (nums[i % nums.size()] <= nums[st.top()]) st.push(i % nums.size());
            else {
                while (!st.empty() && nums[st.top()] < nums[i % nums.size()]){
                    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;
        st.push(0);

        for (int i = 1; i < nums.size() * 2; i++){
            //if (nums[i % nums.size()] <= nums[st.top()]) st.push(i % nums.size());
            // else{}
            while (!st.empty() && nums[st.top()] < nums[i % nums.size()]){
                result[st.top()] = nums[i % nums.size()];
                st.pop();
            }
            st.push(i % nums.size());

        }
        return result;

    }
};

Leetcode42. 接雨水

思路：暴力双指针，时间超时，注意从左向右遍历时，右侧最大值的记录位置，不要将左边的最大值也记录上了

class Solution {
public:
    int trap(vector<int>& height) {
        int result = 0;
        int maxl = INT_MIN;
        int maxr;
        for(int i = 1; i < height.size() - 1; i++){
            for (int j = i - 1; j >= 0; j--){
                if (height[j] > maxl) maxl = height[j];
            }
            // 注意右侧最大值的记录位置，不要将左边的最大值也记录上了
            maxr = height[i + 1];
            for (int j = i + 2; j < height.size(); j++){
                if (height[j] > maxr) maxr = height[j];
            }
            int h = min(maxl, maxr)- height[i];
            cout << h << endl;
            if (h > 0) result += h;

        }
        return result;
    }
};

双指针优化，把每个位置左右两边的最大值提前记录，避免重复比较操作

class Solution {
public:
    int trap(vector<int>& height) {
        int result = 0;
        vector<int> maxl(height.size());
        vector<int> maxr(height.size());
        maxl[0] = height[0];
        maxr[height.size() - 1] = height[height.size() - 1];
        for (int i = 1; i < height.size(); i++){
            maxl[i] = max(height[i], maxl[i - 1]);
        }
        for (int i = height.size() - 2; i >= 0; i--){
            maxr[i] = max(height[i], maxr[i + 1]);
        }

        for (int i = 1; i < height.size() - 1; i++){
            int h = min(maxl[i - 1], maxr[i + 1]) - height[i];
            if (h > 0) result += h;
        }
        
        return result;
    }
};

双指针是按列求的，而单调栈是按行求的，不过感觉理解起来比前一种难一些

class Solution {
public:
    int trap(vector<int>& height) {
        int result = 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()){
                        int h = min(height[i], height[st.top()]) - height[mid];
                        int w = i - st.top() - 1;
                        result += h * w;
                    }
                }
                st.push(i);
            }
        }
        return result;
    }
};

算法训练营第五十九天打卡，看完项目有点学不动了不知道学啥了，看别人的简历和面经心里总是慌慌的，这两天屡屡思路继续学习，不要害怕，不要放弃，加油！！！