408算法题leetcode--第25天

128. 最长连续序列

• 128. 最长连续序列
• 思路：如注释
• 时间和空间：O(n)
• unordered_set: 无序容器，只存key且不重复

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        // 去重
        // 判断每个数是否为序列开头，如果不是就跳过，如果是就往后遍历直到序列结束
        unordered_set<int>sets;
        for(auto it : nums){
            sets.insert(it);
        }
        int ret = 0;
        for(auto it : sets){
            if(!sets.count(it - 1)){
                // 是开头，往后遍历
                int t = 1;
                while(sets.count(it + 1)){
                    it++;
                    t++;
                }
                ret = max(ret, t);
            }
        }
        return ret;
    }
};

739. 每日温度

• 739. 每日温度
• 时间和空间：O(n)
• 单调栈：通常是一维数组，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置，此时我们就要想到可以用单调栈了；空间换时间；用来存放之前遍历过的元素；求比自己大的元素用递增栈（从栈顶到底部）；结果数组：栈顶元素弹出时，用当前下标减去栈顶元素的下标即结果

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        stack<int>stk;  // 记录下标，因为输出下标
        vector<int>v(temperatures.size(), 0);
        stk.push(0);
        int size = temperatures.size();
        for(int i = 1; i < size; i++){
            // 出栈，输出结果
            while(!stk.empty() && temperatures[i] > temperatures[stk.top()]){
                v[stk.top()] = i - stk.top();
                stk.pop();
            }
            stk.push(i);
        }
        return v;
    }
};