广州城乡建设局_网架公司名字大全_搜索引擎的网站_南京百度竞价推广公司排名

解题思路：

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[] heap;private int size;private int capacity;public MinHeap(int capacity) {this.capacity = capacity;this.size = 0;this.heap = new int[capacity + 1];}private int parent(int i) { return i / 2; }private int leftChild(int i) { return 2 * i; }private int rightChild(int i) { return 2 * i + 1; }public void offer(int val) {if (size >= capacity) return;size++;heap[size] = val;siftUp(size);}public int poll() {if (size == 0) throw new IllegalStateException("Heap is empty");int min = heap[1];heap[1] = heap[size];size--;siftDown(1);return min;}public int peek() {if (size == 0) throw new IllegalStateException("Heap is empty");return heap[1];}private void siftUp(int i) {while (i > 1 && heap[i] < heap[parent(i)]) {swap(i, parent(i));i = parent(i);}}private void siftDown(int i) {while (leftChild(i) <= size) {int minChild = leftChild(i);if (rightChild(i) <= size && heap[rightChild(i)] < heap[minChild]) {minChild = rightChild(i);}if (heap[i] <= heap[minChild]) break;swap(i, minChild);i = minChild;}}private void swap(int i, int j) {int temp = heap[i];heap[i] = heap[j];heap[j] = temp;}}
}

复杂度分析：

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