代码随想录算法训练营第58天 | 739.每日温度, 496.下一个更大元素 I

739.每日温度

代码随想录链接

题目

LeetCode-739.每日温度

根据给定的数组, 给出每一位数之后下一位比自己更大的数和自身的索引差.

题目分析

可以两层for循环暴力法来做, 时间复杂度为\(O(n^2)\).

下面是单调栈的写法, 单调栈就是从栈顶到栈底只能存放单调递增或者单调递减的数据(存放索引即可), 当下一位数据的加入使得单调递增或者单调递减不成立时, 将栈内元素不断弹出, 直到栈为空或者剩余元素和要加入的元素形成的栈符合单调递增或者单调递减.

对于本题目, 有三种情况:

• 要加入的元素和栈顶元素相等

  本题要求是下一个更大的元素, 所以栈从栈顶到栈底应该是递增栈, 此时直接将元素入栈即可.

• 要加入的元素小于栈顶元素

  加入比栈顶元素更小的元素不会破坏栈从栈顶到栈底元素递增的状态, 可以直接将元素入栈.

• 要加入的元素大于栈顶元素

  加入的元素比栈顶元素大, 破坏了站从栈顶到栈底递增的状态, 所以需要将栈顶元素不断弹出, 直到栈符合递增的状态. 在不断弹出的过程中, 要加入的元素就是被弹出元素右侧第一个比其大的元素, 进行标记即可.

题解

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        stack<int> st;
        vector<int> result(temperatures.size(), 0);
        st.push(0); // 第一个元素入栈
        for (int i = 1; i < temperatures.size(); i++) { // 遍历后序所有元素
            if (temperatures[i] > temperatures[st.top()]) { // 如果元素大于栈顶元素, 开始弹出并标记
                while (!st.empty() && temperatures[i] > temperatures[st.top()]) {
                    result[st.top()] = i - st.top();
                    st.pop();
                }
                st.push(i);
            } else {    // 元素小于等于栈顶元素, 仅入栈
                st.push(i);
            }
        }
        return result;
    }
};

496.下一个更大元素 I

代码随想录链接

题目

LeetCode-496.下一个更大元素 I

给定两个没有重复元素的数组A和B, A是B的子集, 求A中每一个元素在B中对应的元素的右侧第一个比自己大的元素.

题目分析

在上面一题的基础上, 对B数组仍然调用上一题的逻辑, 但在弹出栈顶元素时, 判断当前栈顶元素是否在A中存在, 若存在, 则将试图入栈的元素标记为A中该元素在B中对应位置右侧存在的第一个比自身大的数.

题解

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        stack<int> st;
        vector<int> result(nums1.size(), -1);
        unordered_map<int, int> map;
        for (int i = 0; i < nums1.size(); i++)
            map[nums1[i]] = i;
        st.push(0);
        for (int i = 1; i < nums2.size(); i++) {
            if (nums2[i] <= nums2[st.top()]) {
                st.push(i);
            } else {
                while (!st.empty() && nums2[i] > nums2[st.top()]) {
                    if (map.count(nums2[st.top()]) > 0) {
                        int index = map[nums2[st.top()]];
                        result[index] = nums2[i];
                    }
                    st.pop();
                }
            }
            st.push(i);
        }
        return result;
    }
};