剑指offer—最小栈(min函数栈) 解答

剑指offer—最小栈(min函数栈)

思路

使用辅助栈存储min函数可能返回的数,利用单调栈特性

  • 单调栈维护:当元素入栈时,非辅助栈正常入栈,辅助栈则先与栈顶元素比较,如果<栈顶元素,说明可以入栈,满足单调性;出栈时,如果出栈元素和栈顶元素相等,则辅助栈可以出栈,否则说明不是最小栈中元素

单调递减栈可以保证栈顶元素永远是最小的,即使你出栈元素,栈内下一个元素依然是栈内当前最小的

  • 单调栈(递减):栈内元素依次递减,最小值在永远栈顶取得,只需维护该栈

(1)辅助栈为空的时候,必须放入新进来的数;

(2)新来的数小于或者等于辅助栈栈顶元素的时候,才放入,特别注意这里“等于”要考虑进去,因为出栈的时候,连续的、相等的并且是最小值的元素要同步出栈;

(3)出栈的时候,辅助栈的栈顶元素等于数据栈的栈顶元素,才出栈。

总结一下:出栈时,最小值出栈才同步;入栈时,最小值入栈才同步。

代码

import java.util.Stack;

public class Solution {

    Stack<Integer> stack = new Stack<>();
    Stack<Integer> minStack = new Stack<>();

    public void push(int x) {
        stack.push(x);
        if(minStack.isEmpty()||x<minStack.peek()){//小于才能入栈
            minStack.push(x);
        }
    }

    public void pop() {
        int x = stack.pop();
        if(x==minStack.peek()){//相等才能出栈
            minStack.pop();
        }
    }

    public int top() {
        return stack.peek();
    }

    public int min() {
        return minStack.peek();
    }
}

扩展—滑动窗口最大值

LeetCode239

给定一个数组 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

思路

  • 方法一:暴力法—在每个窗口中排序,时间复杂度为O(K*N)

  • 方法二:利用单调队列的特性,用双向队列实现

方法一

在每个窗口的循环中,进行排序,把最大的添加到数组中。

方法二

  • 单调队列(递减):从队列头开始,每个元素都比下一个元素大,这样最大的元素就永远是队列头元素。

在数组范围内循环入队元素的索引(位置),方便判断个数、位置(维护队列)

  1. 入队当前元素索引,如果当前元素>队列中元素,则出队到队列中元素>当前元素。执行入队,维护单调队列
  2. 判断当前队列元素个数是否>k,>则说明队头元素需要出队(维护滑动窗口)
  3. 如果窗口形成,每一次循环后都要把新的最大值加入result数组(每次移动一格)
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]

解释过程中队列中都是具体的值,方便理解,具体见代码。
初始状态:队列:{}
i=0,nums[0]=1。队列为空,直接加入。队列:{1}
i=1,nums[1]=3。队尾值为1,3>1,弹出队尾值,加入3。队列:{3}
i=2,nums[2]=-1。队尾值为3,-1<3,直接加入。队列:{3,-1}。此时窗口已经形成,2>=k-1,result=[3]
i=3,nums[3]=-3。队尾值为-1,-3<-1,直接加入。队列:{3,-1,-3}。队首3对应的下标为1,3>=k-1,有效。result=[3,3]
i=4,nums[4]=5。队尾值为-3,5>-3,依次弹出后加入。队列:{5}。此时4>=k-1,有效。result=[3,3,5]
i=5,nums[5]=3。队尾值为5,3<5,直接加入。队列:{5,3}。此时5>=k-1,有效。result=[3,3,5,5]
i=6,nums[6]=6。队尾值为3,6>3,依次弹出后加入。队列:{6}。此时6>=k-1,有效。result=[3,3,5,5,6]
i=7,nums[7]=7。队尾值为6,7>6,弹出队尾值后加入。队列:{7}。此时7>=k-1,有效。result=[3,3,5,5,6,7]

代码

  • 暴力法—在每个窗口中排序,时间复杂度为O(K*N)
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int []result = new int[nums.length-k+1];
        if(nums.length<=0||k==0) return nums;
        for(int i=0;i<nums.length-k+1;i++){
            int max = nums[i];
            for(int j=i;j<k+i;j++){
                if(nums[j]>max){
                    max = nums[j];
                }
            }
            result[i] = max;
        }
        return result;
    }
}
  • 双向队列—单调队列方法
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums.length<=0||k==0) return nums;
        int []result = new int[nums.length-k+1];
        ArrayDeque<Integer> deque = new ArrayDeque<>();//使用数组双向队列实现
        for(int i=0;i<nums.length;i++){
            //删除前面小的元素后,插入当前元素
            while(!deque.isEmpty()&&nums[deque.getLast()]<nums[i])
                deque.pollLast();
            deque.add(i);
            //如果元素个数大于k,删除队头元素
            if(i-deque.getFirst()>=k)
                deque.pollFirst();
            //如果队尾-队头大于k-1,输出队头元素到数组
            if(i>=k-1)
                result[i-k+1] = nums[deque.getFirst()]; 
        }   
        return result;
    }
}
  • 本文作者: dzou | 微信:17856530567
  • 本文链接: http://www.dzou.top/post/min-stack.html
  • 版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处!
  • 并保留本声明和上方二维码。感谢您的阅读和支持!