1. 题目
• https://leetcode-cn.com/problems/valid-parentheses/• https://leetcode-cn.com/problems/min-stack/• https://leetcode-cn.com/problems/largest-rectangle-in-histogram• https://leetcode-cn.com/problems/sliding-window-maximum• https://leetcode-cn.com/problems/design-circular-deque• https://leetcode-cn.com/problems/trapping-rain-water/
2.2 最小栈#155（简单）
class MinStack {//解法一：辅助栈+数栈。辅助栈存最小值，数栈存数就好了.Deque<Integer> xStack;Deque<Integer> minStack;public MinStack() {this.xStack = new LinkedList<Integer>();this.minStack = new LinkedList<Integer>();minStack.push(Integer.MAX_VALUE);}public void push(int val) {xStack.push(val);minStack.push(Math.min(val, minStack.peek()));}public void pop() {xStack.pop();minStack.pop();}public int top() {return xStack.peek();}public int getMin() {return minStack.peek();}}/*** Your MinStack object will be instantiated and called as such:* MinStack obj = new MinStack();* obj.push(val);* obj.pop();* int param_3 = obj.top();* int param_4 = obj.getMin();*/
2.4 滑动窗口最大值#239（困难）
public int[] maxSlidingWindow(int[] nums, int k) {//该解法超时了❌//方法一:暴力解法.时间复杂度O(n^2),空间复杂度O(1)int length = nums.length;int n = length - k + 1;int[] ans = new int[n];for (int i = 0; i <= length - k; ++i) {ans[i] = nums[i];for (int j = i; j < i + k; ++j) {if (nums[j] > ans[i]) {ans[i] = nums[j];}}}return ans;}public int[] maxSlidingWindow(int[] nums, int k) {//方法一:优先队列.时间复杂度O(nlogn),空间复杂度O(n)//涉及到的Java中PriorityQueue的api有：//peek()查看队列中第一个元素。element()方法会抛异常，前者不会。//offer()往队首插入元素。add()会抛异常，前者不会。//poll()获取队首元素并删除。remove()会抛异常，前者不会。int length = nums.length;//队列中存储的(nums[i], index)这样的二元组PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {public int compare(int[] pair1, int[] pair2) {//排序规则是：从大到小，同样大则下标大的大//这里可以写成lambda表达式return pair1[0] != pair2[0] ? pair2[0] - pair1[0] : pair2[1] - pair1[1];}});//初始化优先队列，先放k个数进去for (int i = 0; i < k; ++i) {queue.offer(new int[]{nums[i], i});}int[] ans = new int[length - k + 1];//目前为止的优先队列的第一个元素一定是这k个元素中的最大值。因为从大到小的顺序。//另外[0]这个位置存放的是nums[i]元素,[1]这个位置存放的是下标。ans[0] = queue.peek()[0];for (int i = k; i < length; ++i) {queue.offer(new int[]{nums[i], i});while (queue.peek()[1] <= i - k) {//比较队列中的第一个元素的【下标】是否还在滑动窗口中，不在则出队queue.poll();}//堆顶的元素自然而然就是最大的元素ans[i - k + 1] = queue.peek()[0];}return ans;}public int[] maxSlidingWindow(int[] nums, int k) {//解法三：单调队列。时间复杂度O(n),空间复杂度O(k)int n = nums.length;Deque<Integer> deque = new LinkedList<>();//先初始化k个元素，这个时候窗口还没开始滑动。//这里也能找到最开始的k个元素中的最大值。for (int i = 0; i < k; ++i) {//如果队列不为空并且当前元素大于队尾元素,则让队尾元素出队直到条件不满足while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {deque.pollLast();}//将下标插入到队尾。因为通过下标查找元素比较容易，反之麻烦。deque.offerLast(i);}//一共有n-k+1个元素int[] ans = new int[n - k + 1];//此时的队首元素一定是第一个滑动窗口中的最大值。ans[0] = nums[deque.peekFirst()];for (int i = k; i < n; ++i) {//做法同上一个循环，就不再赘述while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {deque.pollLast();}deque.offerLast(i);//这个循环是为了检查队首的元素是否处于滑动窗口中，不存在则将队首元素出队while (deque.peekFirst() <= i - k) {deque.pollFirst();}ans[i - k + 1] = nums[deque.peekFirst()];}return ans;}public int[] maxSlidingWindow(int[] nums, int k) {//解法三：单调队列优化写法。时间复杂度O(n),空间复杂度O(k)if (nums == null || nums.length < 2) {return nums;}int n = nums.length;//用双端队列并且按照从大到小的顺序存放当前滑动窗口中值最大元素的下标。Deque<Integer> deque = new LinkedList<>();//答案数组咯int[] ans = new int[n - k + 1];//没必要循环到nfor (int i = 0; i < n; ++i) {//保证这个队列依然是从大到小的顺序，否则将队尾小于当前元素的数出队。//直至队列为空或者满足从大到小的顺序。while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {deque.pollLast();}//将当前元素的下标添加到队尾deque.offerLast(i);//判断队首元素是否处于滑动窗口范围内。一次只入队一个，所以只需要检查一次if (deque.peekFirst() <= i - k) {deque.pollFirst();}//判断窗口长度是否足够k长。因为把初始化操作合并到一起了，//所以最开始没有k长的时候要拿出来单独讨论。//足够长就把队首元素放入答案数组，因为队首元素最大。if (i - k + 1 >= 0) {ans[i - k + 1] = nums[deque.peekFirst()];}}return ans;}
2.5 设计循环双端队列#641（中等）
class MyCircularDeque {
/** Initialize your data structure here. Set the size of the deque to be k. */
private int capacity;
private int[] arr;
private int front;
private int rear;
public MyCircularDeque(int k) {
//要多留一个位置来区分空和满
capacity = k + 1;
arr = new int[capacity];
//头指针指向第一个存放元素的位置
front = 0;
//尾指针指向下一个插入元素的位置。
rear = 0;
}
/** Adds an item at the front of Deque. Return true if the operation is successful. */
public boolean insertFront(int value) {
//3.接下来的就随便写就好了没有顺序要求了。
if (isFull()) {
return false;
}
//循环队列记得-1时要加capacity再取余，防止下标出现负数。
//而+1时不需要加capacity直接取余即可。
front = (front - 1 + capacity) % capacity;
arr[front] = value;
return true;
}
/** Adds an item at the rear of Deque. Return true if the operation is successful. */
public boolean insertLast(int value) {
if (isFull()) {
return false;
}
arr[rear] = value;
rear = (rear + 1) % capacity;
return true;
}
/** Deletes an item from the front of Deque. Return true if the operation is successful. */
public boolean deleteFront() {
if (isEmpty()) {
return false;
}
front = (front + 1) % capacity;
return true;
}
/** Deletes an item from the rear of Deque. Return true if the operation is successful. */
public boolean deleteLast() {
if (isEmpty()) {
return false;
}
rear = (rear - 1 + capacity) % capacity;
return true;
}
/** Get the front item from the deque. */
public int getFront() {
if (isEmpty()) {
return -1;
}
return arr[front];
}
/** Get the last item from the deque. */
public int getRear() {
if (isEmpty()) {
return -1;
}
return arr[(rear - 1 + capacity) % capacity];
}
/** Checks whether the circular deque is empty or not. */
public boolean isEmpty() {
//1.先写判空和判满
return front == rear;
}
/** Checks whether the circular deque is full or not. */
public boolean isFull() {
//2.再写判满
return (rear + 1) % capacity == front;
}
}
/**
* Your MyCircularDeque object will be instantiated and called as such:
* MyCircularDeque obj = new MyCircularDeque(k);
* boolean param_1 = obj.insertFront(value);
* boolean param_2 = obj.insertLast(value);
* boolean param_3 = obj.deleteFront();
* boolean param_4 = obj.deleteLast();
* int param_5 = obj.getFront();
* int param_6 = obj.getRear();
* boolean param_7 = obj.isEmpty();
* boolean param_8 = obj.isFull();
*/
若有收获，就点个赞吧
0 人点赞
