155. 最小栈
way1:思路：使用两个栈，栈1存放所有push进的元素，栈2存放当前栈1中最小的元素。当push元素的时候，和最小元素比较一下，如果大于等于当前最小元素则将该元素也push到栈2中，当pop元素时，也和当前最小元素比较一下，如果和当前最小元素相等，则也将栈2元素pop出去，这样就能时刻保证以常数时间复杂度获取到最小的元素。
class MinStack {private Stack<Integer> stack;private Stack<Integer> minStack;/** initialize your data structure here. */public MinStack() {stack = new Stack();minStack = new Stack();}public void push(int x) {stack.push(x);if (minStack.empty() || minStack.peek() >= x) {minStack.push(x);}}public void pop() {if (!stack.empty()){int pop = stack.pop();if (minStack.peek() == pop) {minStack.pop();}}}public int top() {return stack.peek();}public int getMin() {return minStack.peek();}}
way2:其实可以创造一个Node节点，包含当前值和最小值。
class MinStack {private Node head;/** initialize your data structure here. */public MinStack() {head = new Node(-1, Integer.MAX_VALUE, null);}public void push(int x) {head = new Node(x,Math.min(x, head.minVal),head);}public void pop() {head = head.next;}public int top() {return head.val;}public int getMin() {return head.minVal;}class Node {private int val;private int minVal;private Node next;Node (int val, int minVal, Node next) {this.val = val;this.minVal = minVal;this.next = next;}}}
239. 滑动窗口最大值(重点)
方法1：双端队列法
思路：使用一个双端队列，保证队头的元素是当前滑动窗口的最大值，队列里的元素依次减小。
注意点：当窗口往后移动一格时，将队列里面的元素从尾到头和该元素比大小，小的出队，然后放入当前元素
当队头元素不在窗口时，对头出队列。
class Solution {public int[] maxSlidingWindow(int[] nums, int k) {if (nums == null || nums.length < 2) return nums;if (k == 1) return nums;int[] res = new int[nums.length - k + 1];LinkedList<Integer> queue = new LinkedList();for (int i = 0; i < nums.length; i++) {while (!queue.isEmpty() && nums[i] > nums[queue.peekLast()]) {queue.pollLast();}queue.addLast(i);if (i - k + 1 > queue.peekFirst()) {// i-k+1窗口左指针queue.pollFirst();}if (i - k + 1 >= 0) {res[i - k + 1] = nums[queue.peekFirst()];}}return res;}}
方法2：朴素法
记录窗口最大值的索引，每次窗口往右移动1位时，首先比较最大值的索引和窗口的左边界大小，即检查最大值有没有过期，如果过期，则需要在窗口里重新找到最大值，如果没有过期就好办了，只需要比较一下新增的一位是否比当前最大值还大，这样就能快速得到当前窗口的最大值。
这个方法在有些用例下会跑到很慢，比如严格递减的用例，每次窗口右移都会导致最大值过期，性能降为O(n * k);而对于严格递增的用例，效率则最高。综上还是方法1合适
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums == null || nums.length == 0 || k < 2) return nums;
int maxIdx = 0;
int[] res = new int[nums.length - k + 1];
for (int i = 1; i < k; i++) {
if (nums[i] >= nums[maxIdx]) maxIdx = i;
}
for (int right = k - 1; right < nums.length; right++) {
int left = right - k + 1;
if (left > maxIdx) {
maxIdx = left;
for (int i = left; i <= right; i++) {
if (nums[i] >= nums[maxIdx]) maxIdx = i;
}
}else if (nums[right] >= nums[maxIdx]) {
maxIdx = right;
}
res[left] = nums[maxIdx];
}
return res;
}
}
654. 最大二叉树
方法1：递归法
这道题第一思路是用递归法去解决。
class Solution {
public TreeNode constructMaximumBinaryTree(int[] nums) {
if (nums == null || nums.length == 0) return null;
return constructMaximumBinaryTree(nums, 0, nums.length - 1);
}
private TreeNode constructMaximumBinaryTree(int[] nums, int l, int r) {
if (l > r){
return null;
}
if (l == r) {
return new TreeNode(nums[l]);
}
int i = findMaxIndex(nums, l, r);
TreeNode root = new TreeNode(nums[i]);
root.left = constructMaximumBinaryTree(nums, l, i - 1);
root.right = constructMaximumBinaryTree(nums, i + 1, r);
return root;
}
private int findMaxIndex(int[] nums,int l, int r) {
int maxIndex = l, max = nums[l];
for (int i = l + 1; i <= r; i++) {
if (max < nums[i]) {
max = nums[i];
maxIndex = i;
}
}
return maxIndex;
}
}
方法2：单调栈法
分析题目发现，每个结点的父节点其实是左侧第一个大于该节点大的值和右侧第一个大于该节点的值中的最小值，这跟接雨水那道题求洼点的积水一样一样的，单调栈走起啊，维护一个栈，里面的元素只能存单调减小的，一旦遇到一个比栈顶元素大的，说明当前栈顶元素的左右最大值都已找到，然后弹出该元素，后面就可以干活了(找到较小的那一个，然后将其指向栈顶元素)，就这样循环下去。。。
class Solution {
public TreeNode constructMaximumBinaryTree(int[] nums) {
if (nums == null || nums.length == 0) return null;
Stack<TreeNode> stack = new Stack();
for (int i = 0; i < nums.length; i++) {
TreeNode newNode = new TreeNode(nums[i]);
while (!stack.isEmpty() && nums[i] > stack.peek().val){
TreeNode popNode = stack.pop();
if (stack.isEmpty() || stack.peek().val > nums[i]) {
newNode.left = popNode;
} else {
stack.peek().right = popNode;
}
}
stack.push(newNode);
}
TreeNode head = stack.pop();
while (!stack.isEmpty()) {
stack.peek().right = head;
head = stack.pop();
}
return head;
}
}
739. 每日温度
方法1：单调栈法
栈里维护温度递减的索引，一旦遇到一个比当前栈底大的元素，说明遇到了升温，这个弹出元素，计算索引的差值即可，循环下去，最后留在栈里的元素，都说明这些元素的右侧没有比它们大的了。
class Solution {
public int[] dailyTemperatures(int[] T) {
if (T == null || T.length == 0) return T;
int[] res = new int[T.length];
Stack<Integer> stack = new Stack();
for (int i = 0; i < T.length; i++) {
while (!stack.isEmpty() && T[i] > T[stack.peek()]) {
int curIdx = stack.pop();
res[curIdx] = i - curIdx;
}
stack.push(i);
}
return res;
}
}
方法2：动态规划法
从后往前计算，因为最后一位必然是0，相当于初始条件，如果T[i+1]>T[i] 则res[i]=1，否则跳到比T[i+1]大的元素，即T[i+1+res[i+1]]，再跟T[i]比较大小，详细过程如下：
class Solution {
public int[] dailyTemperatures(int[] T) {
if (T == null || T.length == 0) return new int[0];
int[] res = new int[T.length];
for (int i = T.length - 2; i >= 0; i--) {
int j = i + 1;
while (true) {
if (T[j] > T[i]) {
res[i] = j - i;
break;
} else if (res[j] == 0) {
break;
} else {
j = res[j] + j;
}
}
}
return res;
}
}
42. 接雨水
- 方法1：动态规划法
- 方法2：单调栈法
思路：维护一个单调递减栈，当小于栈顶元素时，直接入栈，如果大于栈顶元素，说明栈顶元素所在位置就是洼地，可以先计算洼地的积水。
class Solution {
public int trap(int[] height) {
if (height == null || height.length < 3) return 0;
Stack<Integer> stack = new Stack();
int sum = 0;
for (int i = 0; i < height.length; i++) {
while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
int curIdx = stack.pop();
if (stack.isEmpty()) break;
int leftIdx = stack.peek();
int depth = Math.min(height[i], height[leftIdx]) - height[curIdx];
int width = i - leftIdx - 1;
sum += width * depth;
}
stack.push(i);
}
return sum;
}
}
若有收获，就点个赞吧
0 人点赞
