剑指Offer题解——栈和队列

比眉伴天荒 2023-03-01 09:40 15阅读 0赞

### 文章目录 ###

*   *  剑指 Offer 09. 用两个栈实现队列
     *   *  解法
     *  剑指 Offer 30. 包含min函数的栈
     *   *  解法
     *  剑指 Offer 59 - I. 滑动窗口的最大值
     *   *  双端队列
     *  剑指 Offer 59 - II. 队列的最大值
     *   *  解法
     *  剑指 Offer 11. 旋转数组的最小数字
     *   *  二分查找
         *   *  推荐阅读

## 剑指 Offer 09. 用两个栈实现队列 ##

[剑指 Offer 09. 用两个栈实现队列][Offer 09.]

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

示例 1：
    
    输入：
    ["CQueue","appendTail","deleteHead","deleteHead"]
    [[],[3],[],[]]
    输出：[null,null,3,-1]
    示例 2：
    
    输入：
    ["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
    [[],[],[5],[2],[],[]]
    输出：[null,-1,null,null,5,2]
    提示：
    
    1 <= values <= 10000
    最多会对 appendTail、deleteHead 进行 10000 次调用

### 解法 ###

class CQueue {
        
        Deque<Integer> stack1;
        Deque<Integer> stack2;
        
    
        public CQueue() {
        
            stack1 = new LinkedList<>();
            stack2 = new LinkedList<>();
        }
        
        public void appendTail(int value) {
        
            stack1.offerFirst(value);
        }
        
        public int deleteHead() {
        
            if (stack2.isEmpty()) {
        
                while (!stack1.isEmpty()) {
        
                    stack2.offerFirst(stack1.pollFirst());
                }
            }
            if (stack2.isEmpty()) {
        
                return -1;
            } else {
        
                int deleteItem = stack2.pollFirst();
                return deleteItem;
            }
        }
    }
    
    /**
     * Your CQueue object will be instantiated and called as such:
     * CQueue obj = new CQueue();
     * obj.appendTail(value);
     * int param_2 = obj.deleteHead();
     */

## 剑指 Offer 30. 包含min函数的栈 ##

[剑指 Offer 30. 包含min函数的栈][Offer 30. _min]

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

示例:
    
    MinStack minStack = new MinStack();
    minStack.push(-2);
    minStack.push(0);
    minStack.push(-3);
    minStack.min();   --> 返回 -3.
    minStack.pop();
    minStack.top();      --> 返回 0.
    minStack.min();   --> 返回 -2.
     
    
    提示：
    
    各函数的调用总次数不超过 20000 次

### 解法 ###

class MinStack {
        
        private Deque<Integer> stack;
        private Deque<Integer> minStack;
        private int min;
    
        /** initialize your data structure here. */
        public MinStack() {
        
            stack = new LinkedList<>();
            minStack = new LinkedList<>();
            min = Integer.MAX_VALUE;
        }
        
        public void push(int x) {
        
            stack.offerFirst(x);
            min = Math.min(min, x);
            minStack.offerFirst(min);
        }
        
        public void pop() {
        
            stack.pollFirst();
            minStack.pollFirst();
            min = minStack.isEmpty() ? Integer.MAX_VALUE : minStack.peekFirst();
        }
        
        public int top() {
        
            return stack.peekFirst();
        }
        
        public int min() {
        
            return minStack.peekFirst();
        }
    }
    
    /**
     * Your MinStack object will be instantiated and called as such:
     * MinStack obj = new MinStack();
     * obj.push(x);
     * obj.pop();
     * int param_3 = obj.top();
     * int param_4 = obj.min();
     */

## 剑指 Offer 59 - I. 滑动窗口的最大值 ##

[剑指 Offer 59 - I. 滑动窗口的最大值][Offer 59 - I.]

给定一个数组 nums 和滑动窗口的大小 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
     
    
    提示：
    
    你可以假设 k 总是有效的，在输入数组不为空的情况下，1 ≤ k ≤ 输入数组的大小。

### 双端队列 ###

[详细解题思路][Link 1]

class Solution {
        
        public int[] maxSlidingWindow(int[] nums, int k) {
        
            if (nums.length == 0) {
        
                return new int[0];
            }
            Deque<Integer> deque = new LinkedList<>();
            int size = nums.length;
            int[] res = new int[size - k + 1];
            int index = 0;
            for (int i = 0; i < size; i++) {
        
                // 删除比当前元素小的元素，维持双端队列对头最大
                while (i > 0 && (deque.size() > 0) && nums[i] > deque.peekLast()) {
        
                    deque.pollLast();
                }
                // 当前元素入队
                deque.offerLast(nums[i]);
                // 处理特殊情况，如果最大的值是上一个滑动窗口里面的值，将其删掉。
                if (i >= k && nums[i - k] == deque.peekFirst()) {
        
                    deque.pollFirst();
                }
                // 将结果存到res中
                if (i >= k - 1) {
        
                    res[index++] = deque.peekFirst();
                } 
            }
            return res;
        }
    }

## 剑指 Offer 59 - II. 队列的最大值 ##

[剑指 Offer 59 - II. 队列的最大值][Offer 59 - II.]

请定义一个队列并实现函数 max\_value 得到队列里的最大值，要求函数max\_value、push\_back 和 pop\_front 的均摊时间复杂度都是O(1)。

若队列为空，pop\_front 和 max\_value 需要返回 -1

示例 1：
    
    输入: 
    ["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]
    [[],[1],[2],[],[],[]]
    输出: [null,null,null,2,1,2]
    示例 2：
    
    输入: 
    ["MaxQueue","pop_front","max_value"]
    [[],[],[]]
    输出: [null,-1,-1]
     
    
    限制：
    
    1 <= push_back,pop_front,max_value的总操作数 <= 10000
    1 <= value <= 10^5

### 解法 ###

本算法基于问题的一个重要性质：当一个元素进入队列的时候，它前面所有比它小的元素就不会再对答案产生影响。

举个例子，如果我们向队列中插入数字序列 1 1 1 1 2，那么在第一个数字 2 被插入后，数字 2 前面的所有数字 1 将不会对结果产生影响。因为按照队列的取出顺序，数字 2 只能在所有的数字 1 被取出之后才能被取出，因此如果数字 1 如果在队列中，那么数字 2 必然也在队列中，使得数字 1 对结果没有影响。

按照上面的思路，我们可以设计这样的方法：从队列尾部插入元素时，我们可以提前取出队列中所有比这个元素小的元素，使得队列中只保留对结果有影响的数字。这样的方法等价于要求维持队列单调递减，即要保证每个元素的前面都没有比它小的元素。

class MaxQueue {
        
        Queue<Integer> queue;
        Deque<Integer> maxQueue;
        
        public MaxQueue() {
        
            queue = new LinkedList<>();
            maxQueue = new LinkedList<>();
        }
        
        public int max_value() {
        
            if (maxQueue.isEmpty()) {
        
                return -1;
            }
            return maxQueue.peekFirst();
        }
        
        public void push_back(int value) {
        
            while (!maxQueue.isEmpty() && maxQueue.peekLast() < value) {
        
                maxQueue.pollLast();
            }
            queue.offer(value);
            maxQueue.offerLast(value);
        }
        
        public int pop_front() {
        
            if (queue.isEmpty()) {
        
                return -1;
            } 
            int ans = queue.peek();
            if (ans == maxQueue.peekFirst()) {
        
                maxQueue.pollFirst();
            }
            return queue.poll();
        }
    }
    
    /**
     * Your MaxQueue object will be instantiated and called as such:
     * MaxQueue obj = new MaxQueue();
     * int param_1 = obj.max_value();
     * obj.push_back(value);
     * int param_3 = obj.pop_front();
     */

## 剑指 Offer 11. 旋转数组的最小数字 ##

[剑指 Offer 11. 旋转数组的最小数字][Offer 11.]

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 \[3,4,5,1,2\] 为 \[1,2,3,4,5\] 的一个旋转，该数组的最小值为1。

示例 1：

输入：\[3,4,5,1,2\]  
输出：1  
示例 2：

输入：\[2,2,2,0,1\]  
输出：0

### 二分查找 ###

class Solution {
        
        public int minArray(int[] numbers) {
        
            int left = 0, right = numbers.length - 1;
            while (left < right) {
        
                int mid = left + ((right - left) >> 1);
                if (numbers[mid] < numbers[right]) {
        
                    right = mid;
                } else if (numbers[mid] > numbers[right]) {
        
                    left = mid + 1;
                } else {
        
                    right--;
                }
            }
            return numbers[left];
        }
    }

--------------------

#### 推荐阅读 ####

*  [机器学习资料汇总][Link 2]
 *  [吴恩达《机器学习》视频、作业、源码][Link 3]
 *  [106页《Python进阶》中文版正式发布][106_Python]
 *  [李航《统计学习方法》第二版完整课件][Link 4]
 *  [机器学习数学全书，1900页PDF下载][1900_PDF]

--------------------

![format_png][]

[Offer 09.]: https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/
[Offer 30. _min]: https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof/
[Offer 59 - I.]: https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/
[Link 1]: https://leetcode-cn.com/problems/sliding-window-maximum/solution/shuang-duan-dui-lie-jie-jue-hua-dong-chuang-kou--2/
[Offer 59 - II.]: https://leetcode-cn.com/problems/dui-lie-de-zui-da-zhi-lcof/
[Offer 11.]: https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/
[Link 2]: https://mp.weixin.qq.com/s/3nOkk_Yt9D7Qp1WaWEjyZQ
[Link 3]: https://mp.weixin.qq.com/s/dErZNtBYbVA7ItPm7T_HIw
[106_Python]: https://mp.weixin.qq.com/s/_WEuuxj-QgihijjLz7NJ9g
[Link 4]: https://mp.weixin.qq.com/s/xah47OWuu8ahAUa1aFFo4Q
[1900_PDF]: https://mp.weixin.qq.com/s/9BuyhdwuHiHH3ksVUe44ZQ
[format_png]: /images/20230209/4d2cb9537bca434391bfb1f2aff8033f.png