首页 > 春招冲冲冲 011 补充mysql & 一道题目
头像
gemone
编辑于 2020-12-31 14:18
+ 关注

春招冲冲冲 011 补充mysql & 一道题目

继续备考,写题目笔记花了点时间。

mysql补充了些练习内容。

完成题解。

->寻找柱形最大矩形

粘贴在这。

给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。

求在该柱状图中,能够勾勒出来的矩形的最大面积。

-> leetcode:柱状图的中最大矩形

暴力解法及寻找规律

最直觉的解题方法,就是往暴力解法上走,而用暴力解法我们可以理解题目的意思:

  1. 遍历整个数组,遍历到本位置的时候,以本位置的数字作为高度;
  2. 重新遍历该数组,如果碰到比当前高度小的地方,则记录当前的面积,重置当前的宽度;
  3. 遍历完成后记录当前的面积;

这个思路写成代码:

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        // 暴力
        int res{0};
        for (int i{0}; i<heights.size(); ++i) {
            int height = heights[i];
            int width{0};
            for (int j{0}; j<heights.size(); ++j) {
                if (height > heights[j]) {
                    res = max(width*height, res);
                    width = 0;
                    continue;
                }
                width += 1;
            }
            res = max(width*height, res);
        }
        return res;
    }
};

而当前的代码对于大型用例会超时,毕竟时间复杂度达到了O(N^2)

避免遍历两遍,尽量只遍历一遍完成解答,则需要使用某些方法记录上一个状态,即典型的以空间换时间。

那么使用暴力解法了解到了这道题的本质,就可以选择对应的方案了。

根据示例:[2, 1, 5, 6, 2, 3]

按照暴力解法,可以观察到:

      6
    5 5
    4 4
    3 3   3
2   2 2 2 2
1 1 1 1 1 1

十分直观,凡是连续的相同的数字都可以组成矩形。

思考

所谓面积,而且是矩形的面积,就是找到长和高。

本题目当中寻找最大矩形就是找最大面积的矩形,题目当中,高基本可以很方便得获取到,就是数组中的数字,而大的数字可以作为较小的数字的一部分(反之则不行),因此需要考虑的地方在宽如何去确定。

暴力解法当中是先确定高,在逐步确定宽度,但一旦确定高之后会重新遍历一次整个柱型图,再确定高。

我们要避免回去再遍历一次,尽量在读取当前高度的时候就确定到能够获取的最大宽度,从而使得算法达到优化。

依旧按照示例,我们要做的事情如下:

  1. 遍历到第一个元素是,即2,我们需要确定它最大的宽度,就是往下走,而下一个是1,无法成为2的最大宽度。那么第一个元素能够确定最大的宽度是1。
  2. 第二个元素,是1,往前它可以使用2,往后可以到达最后一个,即最大宽度是6
  3. 同理,往后续一步步地走到底部,一次性确定宽度。

我们需要做的是如何实现,这其中重要的是如何往前走和往后走,而不使用再次遍历的方法。

那么我们应该存储一个可以使用某种方法计算最大宽度(即现在高度的左右边缘)的值,显然无法使用数组中的值,而还能够使用的是其索引,我们先标注一下索引:

      6
    5 5
    4 4
    3 3   3
2   2 2 2 2
1 1 1 1 1 1
- - - - - - 
0 1 2 3 4 5

推断

现在推断:

  1. 0索引,左右边缘是[0, 1)
  2. 1索引,左右边缘是[0, 5]
  3. 2索引,左右边缘是[2, 3]
  4. 3索引,左右边缘是[3, 4)
  5. 4索引,左右边缘是[2, 5]
  6. 5索引,左右边缘是(4, 5]

注意()标记不包含,[]标记包含。

而如何实现这个索引的记录,我们尝试分析:

  1. [0]时,数字2,暂时无法获取最大;
  2. [1]时,数字1,比2小,可以确定2下边无法在往右走,则可以不理会2了,但1没有右边缘;
  3. [2]时,数字5,比1大,还是无法确定两者;
  4. [3]时,数字6,比5大,依旧无法确定;
  5. [4]时,数字2,比6小,则确定6的边界到此处,同时5的边界也应该去确定,但不能在这一次确定,等待下一次,先确定6;
  6. 此时回到[3],已经确定该情况宽度,因此回到[2],确定[2]的宽度;确定宽度的,则不再理会,继续往下走;
  7. 此时我们疑惑[1]会不会确定边界,明显[4]中的2比1大,依旧无法确定1,则继续往下走;
  8. 回到[4],无法确定;
  9. [5]时,数字3,比2大,因此无法确定2边界。但[5]是最后一个索引,因此可以确定3的边界,确定完成后,往回走;
  10. 回到[4][5]中3比2大,则可以确定[4]的边缘了。
  11. [2] [3]已经完成了边缘确定,跳过;
  12. 回到[1],最后一个元素,确定宽度;
  13. [0],已经确定,则跳过;
  14. 流程已经完成
  15. 输出结果

这过程中忽略了具体的计算内容,但可以感觉到这个过程是一个先进后出的过程,从5-7的时候已经发现了这个规律,后面也是一样的,那么我们可以确定使用栈可以实现这个记录。

计算

那么左右边缘如何去实现计算呢?

先将上诉分析的过程用栈模拟一下:

# 1. [0]:2 
stk: 0

# 2. [0]:2 [1]:1
1 < 2
确定 [0],不要了
stk:
[1] 不确定
stk: 1

# 3. [1]:1 [2]:5
不确定
stk: 1 2

# 4. [1]:1 [2]:5 [3]:6
不确定
stk: 1 2 3

# 5. [1]:1 [2]:5 [3]:6 [4]:2
2 < 6
确定[3],不要了
stk: 1 2
2 < 5
确定[2],不要了
stk: 1
2 > 1
[1] 不确定
[4]不确定
stk: 1 4

# 6 [1]:1 [4]:2 [5]:3
[5]不确定
stk: 1 4 5

# 7 结束了,则弹出
stk: 1 4 5
[5] 确定,弹出
[4] 确定,弹出
[1] 确定,弹出

完成

大致流程确定,接下来添加计算过程:

l代表左边缘,r代表右边缘:

# 1. [0]:2 
stk: 0
>>>不计算

# 2. [0]:2 [1]:1
1 < 2
>>>[0]需要计算,左边无,则l:0
>>>右边是[1],不包含,则r:1-1=0
>>>则width = r-l+1 = 1;
确定 [0],不要了
stk:
[1] 不确定
stk: 1

# 3. [1]:1 [2]:5
不确定
stk: 1 2

# 4. [1]:1 [2]:5 [3]:6
不确定
stk: 1 2 3

# 5. [1]:1 [2]:5 [3]:6 [4]:2
2 < 6
>>>[3]需要计算,左边是[2],但5<6,则l:2+1=3
>>>右边是[4],则r:4-1=3
>>>则width = r - l + 1 = 1;
确定[3],不要了
stk: 1 2
2 < 5
>>>[2]需要计算,左边是[1],但1<5,则l:1+1=2
>>>右边是[4],则r:4-1=3
>>>则width=r-l+1=2
确定[2],不要了
stk: 1
2 > 1
[1] 不确定
[4]不确定
stk: 1 4

# 6 [1]:1 [4]:2 [5]:3
[5]不确定
stk: 1 4 5

# 7 结束了,则弹出
此处运算法则不一致
stk: 1 4 5
>>>[5]需要计算,左边是[4],但2<3,则l:4+1=5
>>>右边直接到底,r:5
>>>width=r-l+1=1;
[5] 确定,弹出
>>>[4]需要计算,左边是[1],但1<2,则l:1+1=2
>>>右边直接到底,r:5
>>>width=r-l+1=4
[4] 确定,弹出
>>>[1]需要计算,左边无,则到头,l:0
>>>右边直接到底,r:5
>>>width=r-l+1=5
[1] 确定,弹出

完成

明显此处的计算分两类情况:

  1. 遍历过程中;
  2. 遍历完成,弹出栈的过程;

具体方案

1. 遍历过程中

触发条件:当前元素(index)小于栈顶元素,则开始确定栈顶元素的边缘(宽度);

左边确定:弹出栈顶元素,则左边界为现栈顶元素+1;若无,则为0;

右边确定:index-1;

总宽度:右边确定-左边确定+1;

2. 弹出栈过程(遍历已经完成)

触发条件:栈顶元素(index)都需要确定;

左边确定:弹出栈顶元素,则左边边界为栈顶元素+1;若无,则为0;

右边确定:所要计算的柱形个数-1;

总宽度:右边确定-左边确定+1;

代码实现

好了,思路确定下来,可以开始写代码了。

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        // 栈,存储元素
        std::stack<int> stk;

        // 最大索引
        int max_index=heights.size()-1;

        // 当前元素
        int current{0};
        // 栈顶元素
        int top{0};
        // 左右边界
        int left{0}, right{0};
        // 宽度
        int width{0};
        // 结果,面积
        int area{0};

        // 开始遍历
        for (int i{0}; i<=max_index; ++i) {
            current = i;
            // 如果栈为空 存入 无其他操作,跳过
            if (stk.empty()) {
                stk.push(current);
                continue;
            }

            top = stk.top();
            // 当前元素小于栈顶元素,触发条件
            while (!stk.empty() && (heights[current] < heights[top])) {
                stk.pop();
                left = stk.empty() ? 0 : stk.top() + 1;
                right = current - 1;
                width = right - left + 1;
                area = max(area, width * heights[top]);

                // 新一轮赋值
                top = stk.empty() ? 0 : stk.top();
            }

            stk.push(current);
        }

        // 弹出栈过程
        while (!stk.empty()) {
            top = stk.top();
            stk.pop();

            left = stk.empty() ? 0 : stk.top() + 1;
            right = max_index;
            width = right - left + 1;
            area = max(area, width*heights[top]);
        }

        return area;
    }
};
执行用时:12 ms, 在所有 C++ 提交中击败了93.35% 的用户
内存消耗:8.3 MB, 在所有 C++ 提交中击败了84.19% 的用户

愉快,解决!

如果有不正确的不清楚的,欢迎指正!

冲冲冲!!!

全部评论

(1) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

近期精华帖

热门推荐