Monostone Stack

单调栈，顾名思义，满足单调性的栈结构。举个例子，存在一个栈结构，自底向上的元素为[1, 3, 5, 10, 30, 50]，那么，现欲将新元素20插入其中，需要率先弹出[30, 50]，再将元素20插入，用伪代码描述如下：

insert x
while !stack.empty() && stack.top > x
    stack.pop()

stack.push(x)

再来看实际应用，比如LeetCode中等难度题目402. 移掉K位数字。

移掉K位数字

给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。
注意：

• num 的长度小于 10002 且 ≥ k。
• num 不会包含任何前导零。

  Simple Test Case

  输入: num = "1432219", k = 3
  输出: "1219"
  解释: 移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219。
  -----------
  输入: num = "10200", k = 1
  输出: "200"
  解释: 移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。
  -----------
  输入: num = "10", k = 2
  输出: "0"
  解释: 从原数字移除所有的数字，剩余为空就是0。

  对此，可以采用单调栈结构来择取最小的数字，C++代码如下：

  class Solution {
  public:
      string removeKdigits(string num, int k) {
          string res;
          int n = num.size(), m = n - k;
          for (char c : num) {
              while (k && res.size() && res.back() > c) {
                  res.pop_back();
                  --k;
              }
              res.push_back(c);
          }
          
          res.resize(m);
          //去除前导0， 如10200，k = 1
          while (!res.empty() && res[0] == '0') {
              res.erase(res.begin());
          }
          return res.empty() ? "0" : res;
      }
  };

  再来看单调递增的情况，比如LeetCode困难级别的题目321. 拼接最大数。

  拼接最大数

  给定长度分别为m和n的两个数组，其元素由0-9构成，表示两个自然数各位上的数字。现在从这两个数组中选出k (k <= m + n)个数字拼接成一个新的数，要求从同一个数组中取出的数字保持其在原数组中的相对顺序。

求满足该条件的最大数。结果返回一个表示该最大数的长度为k的数组。

说明: 请尽可能地优化你算法的时间和空间复杂度。

Simple Test Case

输入:
nums1 = [3, 4, 6, 5]
nums2 = [9, 1, 2, 5, 8, 3]
k = 5
输出:
[9, 8, 6, 5, 3]
-----------
输入:
nums1 = [6, 7]
nums2 = [6, 0, 4]
k = 5
输出:
[6, 7, 6, 0, 4]
-----------
输入:
nums1 = [3, 9]
nums2 = [8, 9]
k = 3
输出:
[9, 8, 9]

同样，一个简单的思路是，维护一个大小固定为k的单调栈，每次选出和最大的单调栈，最终得到拼接结果，C++代码如下：

class Solution {
public:
    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
        int m = nums1.size(), n = nums2.size();
        
        vector<int> res;
        for (int i = max(0, k - n); i <= min(k, m); ++i) {
            res = max(res, mergeVector(maxVector(nums1, i), maxVector(nums2, k - i)));
        }
        
        return res;
    }
    
    // 单调栈
    vector<int> maxVector(vector<int> nums, int k) {
        int drop = nums.size() - k;
        
        vector<int> res;
        for (int num : nums) {
            while (drop && res.size() && res.back() < num) {
                res.pop_back();
                --drop;
            }
            res.push_back(num);
        }
        
        res.resize(k);
        return res;
    }
    
    vector<int> mergeVector(vector<int> nums1, vector<int> nums2) {
        vector<int> res;
        while(nums1.size() + nums2.size()) {
            vector<int> &tmp = nums1 > nums2 ? nums1 : nums2;
            res.push_back(tmp[0]);
            tmp.erase(tmp.begin());
        }
        
        return res;
    }
};