496. Next Greater Element I

You are given two arrays(without duplicates)nums1andnums2wherenums1’s elements are subset ofnums2. Find all the next greater numbers fornums1's elements in the corresponding places ofnums2.

The Next Greater Number of a numberxinnums1is the first greater number to its right innums2. If it does not exist, output -1 for this number.

Example 1:

Input: nums1 = [4,1,2], nums2 = [1,3,4,2].
Output: [-1,3,-1]
Explanation:
    For number 4 in the first array, you cannot find the next greater number for it in the second array, so output -1.
    For number 1 in the first array, the next greater number for it in the second array is 3.
    For number 2 in the first array, there is no next greater number for it in the second array, so output -1.Example 2:

Input: nums1 = [2,4], nums2 = [1,2,3,4].
Output: [3,-1]
Explanation:
    For number 2 in the first array, the next greater number for it in the second array is 3.
    For number 4 in the first array, there is no next greater number for it in the second array, so output -1.

Note:

1. All elements in nums1 and nums2 are unique.
2. The length of both nums1 and nums2 would not exceed 1000.

S: stack O(n)

从左往右用stack维护一个递减序列，每次碰到一个大于stack.top()的元素，即为stack中所有比该元素小的元素的next greater element

    vector<int> nextGreaterElement(vector<int>& findNums, vector<int>& nums) {
        unordered_map<int, int> next;
        stack<int> stk;
        for (int num : nums) {
            while (!stk.empty() && stk.top() < num) {
                next[stk.top()] = num;
                stk.pop();
            }
            stk.push(num);
        }
        vector<int> result(findNums.size(), - 1);
        for (int i = 0; i < findNums.size(); ++i) {
            if (next.find(findNums[i]) != next.end()) {
                result[i] = next[findNums[i]];
            }
        }
        return result;
    }

503. Next Greater Element II

Given a circular array (the next element of the last element is the first element of the array), print the Next Greater Number for every element. The Next Greater Number of a number x is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn't exist, output -1 for this number.

Input: [1,2,1]
Output: [2,-1,2]
Explanation: The first 1's next greater number is 2; 
The number 2 can't find next greater number; 
The second 1's next greater number needs to search circularly, which is also 2.

Note: The length of given array won't exceed 10000.

S： stack O(n)

和上题思路一样，维护递减数列。复制数组处理环问题

    vector<int> nextGreaterElements(vector<int>& nums) {
        int n = nums.size();
        vector<int> result(n, -1);
        stack<int> idxstk;
        for (int i = 0; i < n * 2; ++i) {
            int num = nums[i % n];
            while (!idxstk.empty() && nums[idxstk.top() % n] < num) {
                result[idxstk.top() % n] = num;
                idxstk.pop();
            }
            idxstk.push(i);
        }
        return result;
    }

402. Remove K Digits

Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible.

Note:

• The length of num is less than 10002 and will be ≥ k.
• The given num does not contain any leading zero.

Example 1:

Input: num = "1432219", k = 3
Output: "1219"
Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.

Example 2:

Input: num = "10200", k = 1
Output: "200"
Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.

Example 3:

Input: num = "10", k = 2
Output: "0"
Explanation: Remove all the digits from the number and it is left with nothing which is 0.

S1: dfs 遍历所有可能 O(2^n)

S2: greedy O(n)

我们希望结果左侧数字尽量小，类似stack维护一个单调递增的result，遇到比result尾部小的元素就pop_back()直到result尾部小于该元素或pop完k个数，然后push进该元素

    string removeKdigits(string num, int k) {
        string result = "";
        if (num.size() == 0) return result;
        int i = 0;
        while (i < num.size() && k > 0) {
            while (k > 0 && result.size() > 0 && result.back() > num[i]) {
                result.pop_back();
                k--;
            }
            result += num[i++];
        }
        if (k == 0) result += num.substr(i);
        else result = result.substr(0, result.size() - k);
        int zerocount = 0;
        while (result[zerocount] == '0') zerocount++;
        result = result.substr(zerocount);
        return result.empty()? "0" : result;
    }

316. Remove Duplicate Letters

Given a string which contains only lowercase letters, remove duplicate letters so that every letter appear once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

Example:

Given"bcabc"
Return"abc"

Given"cbacdcbc"
Return"acdb"

S: count O(n)

维护一个（伪）单调递增的result（单调递增有个约束条件即该字母以后还会出现）

count记录在第i位时，i之后每个字母出现的次数。

在第i位时若当前char c比result末尾char小，且末尾char之后还会出现，pop末尾char，然后插入c。

记录已插入result的char，避免重复

    string removeDuplicateLetters(string s) {
        vector<int> count(26, 0);
        vector<bool> visited(26, false);
        string result = "";
        for (char c : s) count[c - 'a']++;
        for (char c : s) {
            count[c - 'a']--;
            if (visited[c - 'a']) continue;
            visited[c - 'a'] = true;
            while (result.size() > 0 && c < result.back() && count[result.back() - 'a'] > 0) {
                visited[result.back() - 'a'] = false;
                result.pop_back();
            }
            result += c;
        }
        return result;
    }