当前位置: 首页> 教育> 幼教 > 广州城乡建设局_网架公司名字大全_搜索引擎的网站_南京百度竞价推广公司排名

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

时间:2025/7/11 15:20:44来源:https://blog.csdn.net/qq_45801780/article/details/147166748 浏览次数:0次
广州城乡建设局_网架公司名字大全_搜索引擎的网站_南京百度竞价推广公司排名

在这里插入图片描述

解题思路:

  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 个元素直接入堆。
  • 后续元素与堆顶比较,若当前元素更大,则替换堆顶并调整堆,否则跳过。
  1. 最终结果​: 堆顶元素即为第 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)。
关键字:广州城乡建设局_网架公司名字大全_搜索引擎的网站_南京百度竞价推广公司排名

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: