滑动窗口，双指针，单调队列，单调栈

155. 最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

• push(x) —— 将元素 x 推入栈中。
• pop() —— 删除栈顶的元素。
• top() —— 获取栈顶元素。

• getMin() —— 检索栈中的最小元素。

  
  示例:
  输入：
  [“MinStack”,”push”,”push”,”push”,”getMin”,”pop”,”top”,”getMin”]
  [[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); —> 返回 -3.
minStack.pop();
minStack.top(); —> 返回 0.
minStack.getMin(); —> 返回 -2.

class MinStack {
    Deque<Integer> Stack;
    Deque<Integer> minStack;
    /** initialize your data structure here. */
    public MinStack() {
        Stack=new LinkedList<Integer>();
        minStack=new LinkedList<Integer>();
        minStack.push(Integer.MAX_VALUE);
    }
    public void push(int x) {
        Stack.push(x);
        minStack.push(Math.min(x,minStack.peek()));
    }
    public void pop() {
        Stack.pop();
        minStack.pop();
    }
    public int top() {
        return Stack.peek();
    }
    public int getMin() {
        return minStack.peek();
    }
}

76. 最小覆盖子串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：
输入：s = “ADOBECODEBANC”, t = “ABC”
输出：“BANC”

示例 2：
输入：s = “a”, t = “a”
输出：“a”

提示：

• 1 <= s.length, t.length <= 10
• s 和 t 由英文字母组成

  class Solution {
    public String minWindow(String s, String t) {
        String res="";
        if (s.length() < t.length()) return res;
        int[] need = new int[128];
        char[] S=s.toCharArray();
        int cnt=0;
        // 利用数组来保存字符串 t 中每个元素出现的个数
        for (int i = 0; i < t.length(); i++) {
            need[t.charAt(i)]++;
        }
        for (int a : need) {
            if (a > 0) cnt ++;
        }
        for(int i=0,j=0,c=0;i<s.length();i++){
            // 刚好找到一个字符 计数器 ++
            if(need[S[i]]==1) c++;
            need[S[i]]--;// 不管是不是 t 中的元素，都 --
            while(c==cnt&&need[S[j]]<0) need[S[j++]]++;// 在找到完了元素之后才对指针 j 进行后移
            if(c==cnt){
                // 更新结果
                if(res==""||res.length()>i-j+1)
                    res=s.substring(j,i+1);
            }
        }
        return res;
    }
  }