代码随想录算法训练营打卡Day58 | LeetCode739 每日温度、LeetCode496 下一个更大元素I

摘要

• 单调栈方法的时间复杂度是O(n)，只需要一层循环遍历一次输入数组，代码更简洁，逻辑更巧妙。
• 栈内元素从栈顶到栈底递增（或非递减），找的是任意一个元素的右边第一个比该元素大的元素的位置。

LeetCode739 每日温度

739. 每日温度 - 力扣（Leetcode）

• 这道题目是“单调栈”的入门题目。
• 在一维数组中，寻找任意一个元素的右边第一个比该元素大或者比该元素的小的元素的位置，可以考虑使用单调栈。
• 单调栈的本质是用空间来换时间，用一个栈来记录遍历过的元素的位置和顺序。
• 使用单调栈主要要明确在如下三个判断条件下应该做什么
  1. 当前枚举到的元素nums[i]小于栈顶元素nums[st.top()]
  2. 当前枚举到的元素nums[i]等于栈顶元素nums[st.top()]
  3. 当前枚举到的元素nums[i]大于栈顶元素nums[st.top()]
• 当枚举到一个元素temperatures[i]，我们要找的是temperatures[k], k > i且k - i的值最小的元素的位置，即temperatures[i]的右边第一个比temperatrues[i]大的元素。
• 一开始栈是空的，所以第一个元素当然要入栈，那么要考虑栈空的操作要归入哪种情况，先分析上面提到三种情况，再考虑栈空应该归入哪种情况。从左到右遍历temperatures中的元素。
  1. 当前枚举到的元素temperatures[i]小于栈顶元素temperatures[st.top()]。栈内的元素都是我们遍历过的元素，所以此时temperatures[i]入栈的话，从栈顶到栈底，temperatures的值是递增（或非递减）的。
  2. 当前枚举到的元素temperatures[i]等于栈顶元素temperatures[st.top()]。和第 1 种情况一样，temperatures[i]入栈，从栈顶到栈底，temperatures的值是递增（或非递减）的。
  3. 当前枚举到的元素temperatures[i]大于栈顶元素temperatures[st.top()]。temperatures[st.top()]是已经遍历过的元素，temperatures[i]在temperatures[st.top()]的右边。此时可以记录temperatures[st.top()]右边第一个比它大的元素的位置。
     • 不断弹出栈中的元素并记录栈顶元素的右边第一个比它大的元素的位置，直到栈为空或者栈顶元素比temperatures[i]小。
     • 然后temperatures[i]本身也要求它右边第一个比它大的元素的位置，所以temperatures[i]在栈为空或者不比temperatures[st.top()]大时入栈。

题解代码如下

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        stack<int> st;
        vector<int> res(temperatures.size());

        for (int i = 0; i < temperatures.size(); i++) {
            while (!st.empty() && temperatures[i] > temperatures[st.top()]) {
                res[st.top()] = i - st.top();
                st.pop();
            }
            st.push(i);
        }

        while (!st.empty()) {
            res[st.top()] = 0;
            st.pop();
        }

        return res;
    }
};

其实没有必要清空栈，只需要将res全部初始化为0即可

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        stack<int> st;
        vector<int> res(temperatures.size(), 0);

        for (int i = 0; i < temperatures.size(); i++) {
            while (!st.empty() && temperatures[i] > temperatures[st.top()]) {
                res[st.top()] = i - st.top();
                st.pop();
            }
            st.push(i);
        }

        return res;
    }
};

• 以temperatures = [73, 74, 75, 71, 69, 72, 76, 73]为例来模拟单调栈的工作过程。

1. i = 0时，栈为空，直接入栈

2. i = 1时，temperatures[1] > temperatures[0]，0出栈并记录答案，1入栈。

3. i = 2时，temperatures[2] > temperatures[1]，1出栈并记录答案，2入栈。

4. i = 3时，temperatrues[3] < temperatures[2]，3直接入栈。

5. i = 4时，也是直接入栈

6. i = 5时，4出栈，3出栈，然后temperature[5] < temperature[2]，5入栈。

7. i = 6时，5出栈，2出栈，然后栈为空，6进栈。

8. i = 7，temperatures[7] < temperatures[6]，7入栈。

LeetCode496 下一个更大元素I

496. 下一个更大元素 I - 力扣（Leetcode）

• 这道题目和上一道题的思路是一样的。只是需要区别哪些元素在nums1中，只有在nums1中的元素才需要记录下一个更大元素。并且题目说每个元素的值不重复，所以可以用map<int, int>来记录哪些元素在nums1中以及它们在nums1中的对应下标。
• 然后，按照上一题的方法，求出nums2中每个元素的下一个更大元素，并且记录在nums1中的元素的对应的答案即可。

题解代码如下

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        stack<int> st;
        vector<int> res(nums1.size(), -1);// 找不到下一个更大元素则为-1
        map<int, int> target;
        for (int i = 0; i < nums1.size(); i++) {
            target[nums1[i]] = i;
        }

        for (int i = 0, j = 0; i < nums2.size(); i++) {
            while (!st.empty() && nums2[i] > nums2[st.top()]) {
                if (target.count(nums2[st.top()])) {
                    // 找到下一个更大元素，并且nums2[i]在nums1中，记录答案
                    res[target[nums2[st.top()]]] = nums2[i];
                }
                st.pop();
            }
            st.push(i);
        }

        return res;
    }
};