单调栈单调队列

leetcode155 最小栈

class MinStack {
    private Stack<Integer> stack;
    /** initialize your data structure here. */
    public MinStack() {
        stack = new Stack<>();
    }
    public void push(int val) {
        if(stack.isEmpty()){
            stack.push(val);
            stack.push(val);
        }else{
            int temp = stack.peek();
            stack.push(val);
            if(temp>val){
                stack.push(val);
            }else{
                stack.push(temp);
            }
        }
    }
    public void pop() {
        stack.pop();
        stack.pop();
    }
    public int top() {
        return stack.get(stack.size()-2);
    }
    public int getMin() {
        return stack.peek();
    }
}

leetcode739 每日温度

//v1.0 暴力解法时间复杂度O(n^2)
class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int[] res = new int[temperatures.length];
        for(int i=0;i<temperatures.length-1;i++){
            for(int j=i+1;j<temperatures.length;j++){
                if(temperatures[j]>temperatures[i]){
                    res[i] = j-i;
                    break;
                }
            }
        }
        return res;
    }
}
//v2.0 利用栈
class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int len = temperatures.length;
        int[] res = new int[len];
        //维护一个队列,保存的是数组的下标
        Stack<Integer> stack = new Stack<Integer>();
        stack.push(0);
        for(int i=1;i<len;i++){
            while((!stack.isEmpty())&&temperatures[i]>temperatures[stack.peek()]){
                int temp = stack.pop();
                res[temp] = i-temp;
            }
            stack.push(i);
        }
        return res;
    }
}

剑指59-I 滑动窗口最大值

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums.length==0||k==0) return new int[0];
        Deque<Integer> deque = new LinkedList<Integer>();
        int[] res = new int[nums.length-k+1];
        for(int i=1-k,j=0;j<nums.length;j++,i++){
            if(i>0&&deque.peekFirst()==nums[i-1]){
                deque.removeFirst();
            }
            while(!deque.isEmpty()&&deque.peekLast()<nums[j]){
                deque.removeLast();
            }
            deque.addLast(nums[j]);
            if(j>=k-1){
                res[j-k+1] = deque.peekFirst();
            }
        }
        return res;
    }
}

leetcode42 接雨水

class Solution {
    public int trap(int[] height) {
        Stack<Integer> stack = new Stack<>();
        int len = height.length;
        int res = 0;
        int current=0;
        while(current<len){
            while(!stack.isEmpty()&&height[stack.peek()]<height[current]){
                int top = stack.pop();
                if(stack.isEmpty()){
                    break;
                }
                int boundaryHeight = Math.min(height[current],height[stack.peek()])-height[top];
                int distance = current - stack.peek()-1; 
                res += boundaryHeight*distance;
            }
            stack.push(current++);
        }
        return res;
    }
}