刷题笔记2-队列/栈

括号问题

有效的括号 20

使括号有效的最小添加 921

平衡括号串的最小插入 1541

• 【有效括号】

如果只判断一种括号，则不需要使用栈，通过一次遍历即可解决

bool isValid(string s){
    int left = 0;
    for(char c : s){
        if(c == '('){
            left ++;
        } else if (left > 0){
            left --;
        } else {
            return false;
        }
    }
    
    return left == 0;
}

需要同时判断三种括号是否正确：() [] {}

使用上述方法就显得十分麻烦，应该利用栈结构的特性来解决

#define IS_PUSH(x) (x == '(' || x == '[' || x == '{')

#define IS_MATCH(x, y) \
    ((x == '(' && y == ')') || (x == '[' && y == ']') || (x == '{' && y == '}'))

class Solution {
   public:
    bool isValid(string s) {
        stack<char> stk;
        for (char c : s) {
            if (IS_PUSH(c)) { // 左半括号，压栈
                stk.push(c);
            } else {
                if (stk.empty()) return false; // 缺少左半括号
                char c1 = stk.top();
                if (IS_MATCH(c1, c)) { // 匹配
                    stk.pop();
                } else { // 左右括号不匹配
                    return false;
                }
            }
        }

        return stk.empty(); // 如果栈不为空，缺少右半括号
    }
};

• 【使括号有效的最小添加】

由于只涉及一种括号，就不需要使用栈结构，通过一次遍历即可

int minAddToMakeValid(string s) {
    int left = 0;
    int cnt = 0;
    for (char c : s) {
        if (c == '(') {
            left++;
        } else if (left > 0) {
            left--;
        } else {
            cnt++;
        }
    }
    return left + cnt;
}

• 【平衡括号串的最小插入】

// 比较普通的解法

int minInsertions1(string s) {
    int left = 0;
    int cnt = 0;
    int rightInRow = 0; // 连续右括号的数目
    for (char c : s) {
        if (c == '(') {
            if (rightInRow != 0) {
                if (left > 0) {
                    cnt++;  //增加一个右括号
                    left--;
                } else {
                    cnt += 2;  // 增加一个左括号和右括号
                }
                rightInRow = 0;
            }
            left++;
        } else {
            rightInRow++;
            if (rightInRow == 2) {
                if (left > 0)
                    left--;
                else
                    cnt++;  // 增加一个左括号
                rightInRow = 0;
            }
        }
    }

    if (rightInRow != 0) {  // 多余的右括号
        if (left == 0) {
            cnt += 2;
        } else {
            left--;
            cnt++;
        }
        rightInRow = 0;
    }

    return left * 2 + cnt;
}

// 更加简洁的jie'fa

int minInsertions(string s) {
    int need = 0, cnt = 0;
    for (char c : s) {
        if (c == '(') {
            // 当出现一个左括号时，其前的右括号数目应该为偶数，即need应该为偶数，若为奇数需要插入一个右括号
            if (need % 2 == 1) {
                need--;
                cnt++;  // 插入一个右括号
            }
            need += 2;
        } else {
            need--;
            if (need == -1) {
                cnt++;  // 插入一个左括号
                need =
                    1;  // 由于一个左括号需要两个右括号，所以还需要一个右括号
            }
        }
    }

    return cnt + need;
}

单调栈

单调栈实际上就是栈，只是通过简单的技巧使得其中元素的呈单调排列

可以很好解决【下一个更大元素】的问题

下一个更大元素Ⅰ 496

下一个更大元素Ⅱ 503

每日温度 739

• 【base case】

给定一个数组 nums 返回一个结果数组 res，res[i] 表示 nums[i] 的下一个更大的元素，没有返回 -1

[2, 1, 2, 4, 3] 将每一个元素看成是相应高度的棍子。res[i]就是从nums[i]这根棍子向后所能看到的那个棍子的高度。

vector<int> nextGreaterElement(vector<int> &nums){
    stack<int> stk;
    vector<int> res(nums.size());
    // 从后往前遍历，因为栈是后进先出，从后开始遍历，保证出栈的顺序是从前到后
    for(int i = nums.size() - 1; i >= 0; i--){
        // 如果栈不空 依次取出栈顶元素和当前元素比较
        // 直到找到比当前元素大的那一个
        // 【<= 当前元素的可以从栈顶移除，因为当前元素前面的元素是看不见它们的】
        while(!stk.empty() && stk.top() <= nums[i]){
            stk.pop();
        }
        res[i] = stk.empty() ? -1 : stk.top();
        stk.push(nums[i]);
    }
    return res;
}

• 【下一个更大元素Ⅰ】

nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。

这个问题更难了一些，因为是nums1中的x映射到nums2后的下一个更大元素

/*
	对nums2进行base case的处理，但是将结果存放在map中
	对nums1进行遍历，根据map得到最终结果
*/
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
    vector<int> res(nums1.size());
    unordered_map<int, int> map;

    // 对nums2求每个元素的下一个更大元素
    stack<int> stk;
    for (int i = nums2.size() - 1; i >= 0; i--) {

        while (!stk.empty() && stk.top() <= nums2[i]) {
            stk.pop();
        }

        map[nums2[i]] = stk.empty() ? -1 : stk.top();

        /*
            if (stk.empty()) {
                map[nums2[i]] = -1;
            } else {
                while (!stk.empty() && stk.top() <= nums2[i]) {
                    stk.pop();
                }
                if (stk.empty()) {
                    map[nums2[i]] = -1;
                } else {
                    map[nums2[i]] = stk.top();
                }
            }
        */
        stk.push(nums2[i]);
    }

    for (int i = 0; i < nums1.size(); i++) {
        res[i] = map[nums1[i]];
    }

    return res;
}

• 【每日温度】

base case 的变式，res[i] 是 下一个最大元素 到 nums[i] 的距离

// 栈结构中存放的是 <index, value> 的pair
vector<int> dailyTemperatures1(vector<int>& temperatures) {
    // <pos, value>
    stack<pair<int, int>> stk;
    vector<int> res(temperatures.size());
    for (int i = temperatures.size() - 1; i >= 0; i--) {
        while (!stk.empty() && stk.top().second <= temperatures[i]) {
            stk.pop();
        }
        res[i] = stk.empty() ? 0 : stk.top().first - i;
        stk.push({i, temperatures[i]});
    }

    return res;
}

// 栈结构存放的index
vector<int> dailyTemperatures(vector<int>& temperatures) {
    stack<int> stk;  // 存放索引
    vector<int> res(temperatures.size());
    for (int i = temperatures.size() - 1; i >= 0; i--) {
        while (!stk.empty() && temperatures[stk.top()] <= temperatures[i]) {
            stk.pop();
        }
        res[i] = stk.empty() ? 0 : stk.top() - i;
        stk.push(i);
    }

    return res;
}

• 【下一个更大元素Ⅱ】

引入了环形数组，但是可以通过模运算来模拟环形数组的效果

vector<int> nextGreaterElements(vector<int>& nums) {
    stack<int> stk;
    vector<int> res(nums.size());

    // 利用单调栈时将数组长度翻倍，但是循环数组的效果是用模运算体现出来的
    for (int i = 2 * nums.size() - 1; i >= 0; i--) {
        int j = i % nums.size(); // 对应的下标
        while (!stk.empty() && stk.top() <= nums[j]) {
            stk.pop();
        }
        if (i < nums.size()) {
            res[i] = stk.empty() ? -1 : stk.top();
        }
        stk.push(nums[j]);
    }

    return res;
}

单调队列

滑动窗口最大值 239

【题目】给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

最主要是利用了【双端队列】，或者说是 利用可以在头部尾部增减元素的数据结构

难点在于：为什么窗口和队列中的元素可以不同步？

队列中的元素x，是在 比它更大元素y插入时【注意y是在x后面的】 被移出的。由于只是求窗口中的最大值，所以结果是不受影响的。

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    vector<int> res(nums.size() - k + 1);
    deque<int> dq;
    
    int cnt = 0; // 记录队列中的元素个数
    int index = 0; // 结果集的下标
    
    for(int i = 0; i < nums.size(); i++){
        // 将队列中所有比 nums[i] 小的元素移出 => 使得队列中元素呈单调递减排列
        /*
        	1、这样使得队列头部元素就是队列中最大元素，即窗口最大值
        	2、为什么要移出，而不是让它们排列
        		2.1、如果不将它们移出，只是排列，当窗口需要实际移出它们时就会变得困难
        		2.2、而且在排列时就移出，不会对正确性产生影响，队列和窗口中的元素不是同时移出，
        		会出现四种情况: 有两种是对应的，即窗口中和队列中都有某元素、都没有某元素  这两种肯定是正确的。另外两种:
        		
        			2.2.1、窗口中有该元素，而队列中没有。队列中没有 说明该元素不是队列中最大元素，在比其更大的元素插入时被移出，
        			还说明该元素在nums中的位置是先于比它更大的元素的，所以窗口也是更早将其移出的。
        			由于只需要求窗口最大元素，所以没有影响
        			2.2.2、窗口中没有某元素，而队列中有。
        					如果该元素不是最大元素的话，同2.2.1 在窗口实际移除它之前，队列就已经把它给移出了，故不存在该情况
        					如果该元素是最大元素的话，那么在窗口移出它的同时，队列会移出它，即代码29、30行所做，也不会存在该情况
        	3、将元素从尾部取出比较的，这样才能保证是单调递减 => 所以需要双端队列
        */
        while(!dq.empty() && dq.back() < nums[i]){
            dq.pop_back();
        }
        dq.push_back(nums[i]);
        cnt++;
        
        // 窗口元素满了
        if(cnt == k){
            res[index++] = dq.front(); // 最大元素就是队列头部元素
            // 如果窗口需要移出的是最大元素，那队列就要移出该元素。
            // 否则不需要，因为更早时候已经移出了
            if(dq.front() == nums[i - k + 1]){
                dq.pop_front();
            }
            cnt --;
        }
    }
    
    return res;
}

数组去重

去除重复字母 316

不同字符的最小子序列 1081

给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。

例如

输入：s = "bcabc"
输出："abc"

// 利用栈结构
string removeDuplicateLetters(string s) {
    int* cnts = new int[26]{0};  // 记录字符串中每种字符的数量
    bool* isInStk = new bool[26]{false}; // 记录对应字符在栈中是否出现
	
    // 统计字符串中每种字符的数量
    for (int i = 0; i < s.size(); i++) {
        cnts[s[i] - 'a']++;
    }

    stack<char> stk;
    for (int i = 0; i < s.size(); i++) {
        
        cnts[stk.top() - 'a']--;
        
        if (isInStk[s[i] - 'a']) { // 栈中已经存在该字符
            continue;
        }

        while (!stk.empty() &&
               stk.top() >= s[i] && // 前面的字符字典序更大
               cnts[stk.top() - 'a'] > 1) { // 而且后面还存在该字符 就可以将该字符移除
            isInStk[stk.top() - 'a'] = false;
            stk.pop();
        }

        stk.push(s[i]);
        isInStk[s[i] - 'a'] = true;
    }

    string ans = "";
    while (!stk.empty()) {
        ans += stk.top();
        stk.pop();
    }

    reverse(ans.begin(), ans.end());

    return ans;
}


// 直接使用字符串
string smallestSubsequence(string s) {
    int* cnts = new int[26]{0};
    bool* isInStk = new bool[26]{false};

    for (int i = 0; i < s.size(); i++) {
        cnts[s[i] - 'a']++;
    }

    string stk;
    for (int i = 0; i < s.size(); i++) {
        if (isInStk[s[i] - 'a']) {
            cnts[s[i] - 'a']--;
            continue;
        }

        while (!stk.empty() && stk.back() >= s[i] &&
               cnts[stk.back() - 'a'] > 1) {
            isInStk[stk.back() - 'a'] = false;
            cnts[stk.back() - 'a']--;
            stk.pop_back();
        }

        stk.push_back(s[i]);
        isInStk[s[i] - 'a'] = true;
    }

    return stk;
}