力扣100题——栈和堆
栈
每日温度
题目
739. 每日温度 - 力扣(LeetCode)
思路
利用栈先进后出的特性
- 首先当栈为空时,元素入栈
- 当栈不为空,并且temperatures[i]大于temperatures[stack.peek()]时,不断更新result数组的值,直到栈中元素温度大于当前温度或者栈为空时停止
代码
public int[] dailyTemperatures(int[] temperatures) {int[] result = new int[temperatures.length];Stack<Integer> stack = new Stack<>();for (int i = 0; i < temperatures.length; i++) {if(stack.isEmpty()){stack.push(i);continue;}while(!stack.isEmpty()&&temperatures[i]>temperatures[stack.peek()]) {result[stack.peek()] = i - stack.peek();stack.pop();}stack.push(i);}while(!stack.empty()){result[stack.pop()]=0;}return result;}
最小栈
题目
155. 最小栈 - 力扣(LeetCode)
思路
使用两个栈,一个栈存储元素,一个栈同步存储当前栈中的最小值。
在push和pop的时候同时更新minStack,在getMin时返回minStack的元素即可
代码
class MinStack {private Stack<Integer> stack;private Stack<Integer> minStack;public MinStack() {stack = new Stack<>();minStack = new Stack<>();minStack.push(Integer.MAX_VALUE);}public void push(int val) {stack.push(val);minStack.push(Math.min(val, minStack.peek()));}public void pop() {stack.pop();minStack.pop();}public int top() {return stack.peek();}public int getMin() {return minStack.peek();}
}
柱状图中最大的矩形
题目
84. 柱状图中最大的矩形 - 力扣(LeetCode)
思路
解题思路
-
暴力解法:对于每根柱子,向左、向右找到第一个比它小的柱子,计算宽度,然后计算面积。这个方法时间复杂度为 O(n²),效率较低。
-
优化解法(单调栈):通过单调递增栈来存储柱子的索引,栈中的柱子高度按从小到大的顺序排列。每当遇到一个比栈顶柱子高度低的柱子时,弹出栈顶,计算以该柱子为最短边的矩形的面积。
单调栈方法详细步骤
- 遍历数组:对于每一个柱子,如果当前柱子高度小于栈顶柱子的高度,说明以栈顶柱子为最短边的矩形的右边界确定了。
- 计算面积:
- 弹出栈顶元素,计算以该元素为高度的矩形面积。
- 宽度为弹出元素的左右两边第一个小于它的元素之间的距离(可以通过栈内索引计算)。
- 更新最大面积:更新最大矩形面积。
- 处理完数组后:继续处理栈中剩余的柱子,计算它们对应的矩形面积。
代码
public int largestRectangleArea(int[] heights) {if(heights == null || heights.length == 0){return 0;}if(heights.length == 1){return heights[0];}Stack<Integer> stack = new Stack<>();int max = 0;for(int i=0;i<=heights.length;i++){int h = (i == heights.length)?0:heights[i];while(!stack.isEmpty()&&heights[stack.peek()]>h){int height = heights[stack.pop()];int width = stack.isEmpty()?i:i - stack.peek()-1;max = Math.max(max,height*width);}stack.push(i);}return max;}
堆
堆(Heap)是一种特殊的树形数据结构,它满足以下两个主要性质:
- 完全二叉树:堆必须是一棵完全二叉树。即除了最后一层外,每一层的节点都是满的,且最后一层的节点从左到右依次填充。
- 堆的性质:
- 最大堆(Max Heap):对于最大堆,任意节点的值总是大于或等于其子节点的值,也就是说,堆顶(根节点)是整个堆中最大的元素。
- 最小堆(Min Heap):对于最小堆,任意节点的值总是小于或等于其子节点的值,即堆顶是最小的元素。
数组中的第K个最大值
题目
215. 数组中的第K个最大元素 - 力扣(LeetCode)
思路
- 使用一个大小为
k
的最小堆来存储数组中的前k
个元素。 - 遍历数组中的每个元素:
- 如果堆的大小小于
k
,直接将当前元素加入堆。 - 如果堆的大小等于
k
,且当前元素大于堆顶元素(堆顶是堆中的最小元素),则弹出堆顶元素,插入当前元素。
- 如果堆的大小小于
- 遍历结束后,堆顶元素就是数组中第
k
大的元素,因为堆中存储了k
个最大的元素,而堆顶是最小的那个。
代码
public int findKthLargest(int[] nums, int k) {PriorityQueue<Integer> queue = new PriorityQueue<>();for (int num : nums) {if (queue.size() < k) {queue.offer(num);} else if(queue.peek() < num) {queue.poll();queue.offer(num);}}return queue.peek();}
前K个高频元素
题目
347. 前 K 个高频元素 - 力扣(LeetCode)
思路
- 使用最小堆+哈希表
- 思路和上一题基本一致,变的是堆中存储的元素。
代码
public int[] topKFrequent(int[] nums, int k) {HashMap<Integer,Integer> map = new HashMap<>();for(int num : nums){if(map.containsKey(num)){map.put(num,map.get(num)+1);}else {map.put(num,1);}}PriorityQueue<Map.Entry<Integer, Integer>> minHeap = new PriorityQueue<>(k,Comparator.comparingInt(Map.Entry::getValue));for (Map.Entry<Integer, Integer> entry : map.entrySet()) {if(minHeap.size() < k){minHeap.add(entry);}else if(minHeap.peek().getValue() < entry.getValue()){minHeap.poll();minHeap.add(entry);}}int[] result = new int[k];for(int i=0;i<k;i++){result[i] = minHeap.poll().getKey();}return result;}
数据流中的中位数
题目
295. 数据流的中位数 - 力扣(LeetCode)
思路
- 最大堆维护较小的一半元素(左半部分),堆顶是这部分的最大值。
- 最小堆维护较大的一半元素(右半部分),堆顶是这部分的最小值。
- 中位数可以根据两个堆的大小情况动态获取:
- 如果元素总数是奇数,最大堆的堆顶元素就是中位数。
- 如果元素总数是偶数,则中位数是最大堆堆顶和最小堆堆顶的平均值
代码
class MedianFinder {private Queue<Integer> minQueue;private Queue<Integer> maxQueue;public MedianFinder() {minQueue = new PriorityQueue<>(Collections.reverseOrder());maxQueue = new PriorityQueue<>();}public void addNum(int num) {maxQueue.offer(num);minQueue.offer(maxQueue.poll());if (minQueue.size() > maxQueue.size()) {maxQueue.offer(minQueue.poll());}}public double findMedian() {if(minQueue.size() < maxQueue.size()) {return maxQueue.peek();}else {return (minQueue.peek()+maxQueue.peek())/2.0;}}
}