汪图南
  • RAG

    • RAG
  • 快速入门
  • 高级技巧
前端面试之道
  • 打包工具

    • Webpack
    • Rollup
  • TypeScript

    • TypeScript基础
    • TypeScript类型挑战
  • CSS预编译器

    • SASS
  • 自动化测试

    • Vue应用测试
  • Vue2.0源码分析
  • Vue3.0源码分析
  • 数据结构和算法(基础)
  • LeetCode(刷题)
  • JavaScript书籍

    • 你不知道的JavaScript(上)
    • 你不知道的JavaScript(中下)
    • JavaScript数据结构和算法
    • JavaScript设计模式与开发实践
    • 深入理解ES6
  • Git书籍

    • 精通Git
Github
  • RAG

    • RAG
  • 快速入门
  • 高级技巧
前端面试之道
  • 打包工具

    • Webpack
    • Rollup
  • TypeScript

    • TypeScript基础
    • TypeScript类型挑战
  • CSS预编译器

    • SASS
  • 自动化测试

    • Vue应用测试
  • Vue2.0源码分析
  • Vue3.0源码分析
  • 数据结构和算法(基础)
  • LeetCode(刷题)
  • JavaScript书籍

    • 你不知道的JavaScript(上)
    • 你不知道的JavaScript(中下)
    • JavaScript数据结构和算法
    • JavaScript设计模式与开发实践
    • 深入理解ES6
  • Git书籍

    • 精通Git
Github
  • 介绍

    • 介绍
  • 推荐

    • LeetCode刷题推荐
  • 链表

    • 目录
    • 简单
    • 中等
    • 困难
  • 栈

    • 目录
    • 简单
    • 中等
    • 困难
  • 队列

    • 目录
    • 简单
    • 中等
    • 困难
  • 哈希表

    • 目录
    • 简单
    • 中等
    • 困难
  • 二叉树

    • 目录
    • 简单
    • 中等
    • 困难
  • 堆

    • 目录
    • 简单
    • 中等
    • 困难
  • 图

    • 目录
    • 简单
    • 中等
    • 困难
  • 搜索

    • 目录
    • 简单
    • 中等
    • 困难

困难

84.柱状图中最大的矩形

84.柱状图中最大的矩形

方法一:暴力法

注意

能运行测试用例,但提交会判定超时

// n为数组的长度
// 时间复杂度:O(n²),外层for循环 + 内存while循环
// 空间复杂度:O(1),仅变量存储开销
var largestRectangleArea = function(heights) {
  const len = heights.length;
  let result = 0;
  for(let i = 0; i < len; i++) {
    const currHeight = heights[i]
    let left = i;
    let right = i;

    while(left > 0 && heights[left - 1] >= currHeight) {
      left--;
    }
    while(right < len - 1 && heights[right + 1] >= currHeight) {
      right++;
    }

    const width = right - left + 1;
    result = Math.max(result, width * currHeight);
  }
  return result;
};

方法二:单调栈 + 空间优化

// n为数组的长度
// 时间复杂度:O(n),遍历数组
// 空间复杂度:O(n),栈和预处理数组(left,right)的存储开销
var largestRectangleArea = function(heights) {
  const length = heights.length;
  const left = new Array(length).fill(-1);
  const right = new Array(length).fill(length);
  const stack = [];
  let result = 0;

  for(let index = 0; index < length; index++) {
    while(stack.length > 0 && heights[index] < heights[stack[stack.length - 1]]) {
      right[stack.pop()] = index;
    }
    left[index] = stack.length === 0 ? -1 : stack[stack.length - 1]
    stack.push(index);
  }

  for(let index = 0; index < length; index++) {
    const height = heights[index];
    const width = right[index] - left[index] - 1;
    result = Math.max(result, height * width);
  }
  return result;
}

方法三:单调栈 + 哨兵

// n为数组的长度
// 时间复杂度:O(n),遍历数组
// 空间复杂度:O(n),栈和添加了哨兵的新数组的存储开销
var largestRectangleArea = function(heights) {
  const newHeights = [0, ...heights, 0];
  const length = newHeights.length;
  const stack = new Array(length).fill(0);
  let result = 0;
  for (let index = 0; index < length; index++) {
    while(newHeights[index] < newHeights[stack[stack.length - 1]]) {
      const height = newHeights[stack.pop()];
      const width = index - stack[stack.length - 1] - 1;
      result = Math.max(result, width * height);
    }
    stack.push(index);
  }

  return result;
}
最后更新时间: 2025/5/6 15:36
贡献者: wangtunan
Prev
中等