LeetCode 解题思路 37（Hot 100）

解题思路：

1. 初始化： 初始化最大举行 max 和栈 stack。
2. 左右补零： 考虑柱子递增的边界情况， 初始化填充柱状图 newHeights。
3. 遍历处理： 对于每一根遍历到的柱子 newHeights[i]，若柱子高度小于栈口索引，计算左边最大矩形面积：

• 右边界索引：i，栈口元素索引：stack.pop()，左边界索引：stack.peek()。
• 当前宽度：i - left - 1，当前高度：newHeights[mid]。

Java代码：

class Solution {int largestRectangleArea(int[] heights) {int max = 0;Deque<Integer> stack = new LinkedList<Integer>();int[] newHeights = new int[heights.length + 2];for (int i = 0; i < heights.length; i++)newHeights[i + 1] = heights[i];newHeights[0] = newHeights[heights.length + 1] = 0;for (int i = 0; i < newHeights.length; i++) {while (!stack.isEmpty() && newHeights[i] < newHeights[stack.peek()]) {int right = i;int mid = stack.pop();if (!stack.isEmpty()) {int left = stack.peek();int w = right - left - 1;int h = newHeights[mid];max = Math.max(max, w * h);}}stack.push(i);}return max;}
}

复杂度分析：

• 时间复杂度： O(n)。
• 空间复杂度： O(n)。

解题思路：

1. 维护大小为k的最小堆​​： 堆顶始终是当前堆中最小的元素。
2. 遍历数组：

• 前 k 个元素直接入堆。
• 后续元素与堆顶比较，若当前元素更大，则替换堆顶并调整堆，否则跳过。

3. 最终结果​： 堆顶元素即为第 k 大元素。

Java代码：

class Solution {public int findKthLargest(int[] nums, int k) {MinHeap minHeap = new MinHeap(k);for (int num : nums) {if (minHeap.size < k) {minHeap.offer(num);} else if (num > minHeap.peek()) {minHeap.poll();minHeap.offer(num);}}return minHeap.peek();}static class MinHeap {private int capacity;private int size;private int[] heap;public MinHeap(int capacity) {this.capacity = capacity;this.size = 0;this.heap = new int[capacity + 1];}private int parent(int index) { return index / 2; }private int leftChild(int index) { return index * 2; }private int rightChild(int index) { return index * 2 + 1; }public int peek() {if (size == 0) throw new IllegalStateException();return heap[1];}public void offer(int value) {if (size == capacity) return;heap[++size] = value;siftUp(size);}public int poll() {if (size == 0) throw new IllegalStateException();int min = heap[1];heap[1] = heap[size--];siftDown(1);return min;}private void siftUp(int index) {while (index > 1 && heap[index] < heap[parent(index)]) {swap(index, parent(index));index = parent(index);}} private void siftDown(int index) {while (leftChild(index) <= size) {int minChild = leftChild(index);if (rightChild(index) <= size && heap[rightChild(index)] < heap[minChild])minChild = rightChild(index);if (heap[index] <= heap[minChild]) break;swap(index, minChild);index = minChild;}}private void swap(int i, int j) {int temp = heap[i];heap[i] = heap[j];heap[j] = temp;}}
}

复杂度分析：

• 时间复杂度： O(nlogk)。
• 空间复杂度： O(k)。