JLUVicent

496下一个更大元素I&739每日温度

 
  • 2023年 04月13日
  • 0 阅读

day58

739.每日温度

题目链接：739. 每日温度

解题思路：参考 视频

本题首先想到的是两层for循环，代码如下：

// 啪一下，很快啊，超时了。。。
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        vector<int> answer(temperatures.size(),0);
        for( int i = 0; i < temperatures.size()-1; i++){
            for( int j = i+1; j < temperatures.size(); j++){
                if(temperatures[i] < temperatures[j]){
                    answer[i] = j-i;
                    break;
                }
            }
        }
        return answer;
    }
};

单调栈方法

单调栈：通常用于寻找一维数组里面任何一个元素的左边或者右边第一个比自己大或者小的元素的位置，使用单调栈，时间复杂度为O(n)

单调栈的本质就是用空间换时间，整个数组只需要遍历一次。

用一个栈来记录遍历过的元素

栈里面存放数组中元素的下标，这样更容易记录

如果求一个元素右边第一个更大元素，单调栈就是递增的，如果求一个元素右边第一个更小元素，单调栈就是递减的。

三种判断条件（第一种和第二种可以放一块）

  • 当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况
  • 当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况
  • 当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        // 时间：O(n)
        // 空间：O(n)
        vector<int> answer(temperatures.size(),0);
        stack<int> st;
        st.push(0); //第一个元素下标入栈
        for( int i = 1; i < temperatures.size(); i++){
            if( temperatures[i] <= temperatures[st.top()]){
                st.push(i);
            }else{
                while( !st.empty() && temperatures[i] > temperatures[st.top()]){
                    answer[st.top()] = i - st.top();
                    st.pop();
                }
                st.push(i); //当前元素也要push进去
            }
        }
        return answer;
    }
};

496.下一个更大元素I

题目链接：496. 下一个更大元素 I

解题思路：参考 视频

本题和上一题基本相同，需要在两个数组之间建立一个哈希映射，然后使用单调栈来解决

class Solution {
public:
    //时间换空间
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int,int> umap;
        for( int i = 0; i < nums1.size(); i++){
            umap[nums1[i]] = i;
        }
        vector<int> answer(nums1.size(),-1);
        stack<int> st;
        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()]){
                    auto iter = umap.find(nums2[st.top()]);
                    if( iter != umap.end()){
                        answer[iter->second] = nums2[i];
                    }
                    st.pop();
                }
                st.push(i);
            }
        }
        return answer;

    }
};

当然也可以直接暴力解决

        vector<int> answer(nums1.size(),-1);
        for( int i = 0; i < nums1.size(); i++){
            for( int j = 0; j < nums2.size(); j++){
                if( nums1[i] == nums2[j]){
                    for( int k = j+1; k < nums2.size(); k++){
                        if(nums2[k] > nums2[j]){
                            answer[i] = nums2[k];
                            break;
                        }
                    }
                    break;
                }
            }
        }
        return answer;
搜索