LeetCode算法学习之--Stack--柱状图中的最大矩形

大家好今天给大家分享下一道 LeetCode 困难难度 的题目[柱状图中最大的矩形]

题目

分析

解法一：stack+array

思维借鉴leetcode-cn.com/problems/la…

思路
1.迭代每个柱子的高度求面积
2.当高度有的时候就要求最大宽度，
3.为了求最大宽度必须找到比它高度矮的左边界和右边界
4.使用stack的机制
    1.stack的最底层一定是放访问过的元素中最小的那个高度，
    2.如果新的柱子高度比前一个大则往stack中push新的元素
    3.当遇到了比stack顶层的柱子还小的时候，说明已经找到了右边界，则可以开始stack中存储的柱子的面积
    4.把计算过的柱子pop掉，还是保持stack 最底层是访问过的最小的那个高度
    5.开始继续循环步骤2
    6.当迭代完整个数组，需要清空stack，同时计算面积
5.设置每个主题的左边界 left 和有边界right
6.最后统计数据

*/
var largestRectangleArea = function (heights) {
  // 用来存放元素的索引
  const stack = [];
  //   所有柱子的左边界的索引
  let left = [];
  //   所有柱子的右边界的索引
  let right = new Array(heights.length);
  right.fill(heights.length);
  let max = 0;

  for (let i = 0; i < heights.length; i++) {
    //  如果stack 有值，且新元素大于stack的顶层元素，则更换stack 这些元素的右边界
    while (stack.length && heights[stack[stack.length - 1]] >= heights[i]) {
      right[stack[stack.length - 1]] = i;
      stack.pop();
    }
    // 如果stack 没有值 则取值-1，如果有值则把边界变成stack中的最后一个值
    left[i] = stack.length === 0 ? -1 : stack[stack.length - 1];
    // stack 中放入当前元素的索引
    stack.push(i);
  }

  //   统计数据
  for (let i = 0; i < heights.length; i++) {
    max = Math.max(heights[i] * (right[i] - left[i] - 1), max);
  }

  return max;
};

/* 复杂度
时间 O(n)
空间 O(n)
*/

解法二：暴力（超时）

思路
1.迭代每个柱子，寻找当前柱子能获得的最大的面积
2.向左找边界 向右找边界
*/

var largestRectangleArea = function (heights) {
  let max = 0;

  for (let i = 0; i < heights.length; i++) {
    const height = heights[i];
    let left = i;
    let right = i;

    // 向左找边界
    while (left > -1) {
      const leftHeight = heights[left];
      if (leftHeight < height) {
        break;
      } else {
        left--;
      }
    }

    /* 向右找边界 */
    while (right < heights.length) {
      const rightHeight = heights[right];
      if (rightHeight < height) {
        break;
      } else {
        right++;
      }
    }
    // 更新最小面积
    max = Math.max(max, height * (right - left - 1));
  }

  return max;
};
/* 复杂度
时间 O(n^2)
空间 O(1)
*/

总结

这道题不是很容易理解，但是核心就是利用stack来存储最左边界防止重复查找，因为在暴力法中就多了很多向左查找的重复动作

大家可以看看我分享的一个专栏（前端搞算法）里面有更多关于算法的题目的分享，希望能够帮到大家，我会尽量保持每天晚上更新，如果喜欢的麻烦帮我点个赞，十分感谢

文章内容目的在于学习讨论与分享学习算法过程中的心得体会，文中部分素材来源网络，如有侵权，请联系删除，邮箱 182450609@qq.com