《剑指 Offer》专项突破版 - 面试题 38、39 和 40 : 通过三道面试题详解单调栈（C++ 实现）

2024-02-10 22:52
文章标签 c++ 实现 详解 面试题 offer 40 38 39 单调 突破 专项 三道

本文主要是介绍《剑指 Offer》专项突破版 - 面试题 38、39 和 40 : 通过三道面试题详解单调栈（C++ 实现），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

面试题 38 : 每日温度

面试题 39 : 直方图最大矩形面积

方法一、暴力求解

方法二、递归求解

方法三、单调栈法

面试题 40 : 矩阵中的最大矩形

 

面试题 38 : 每日温度

题目：

输入一个数组，它的每个数字是某天的温度。请计算每天需要等几天才会出现更高的温度。例如，如果输入数组 [35, 31, 33, 36, 34]，那么输出为 [3, 1, 1, 0, 0]。由于第 1 天的温度是 35℃，要等 3 天才会出现更高的温度 36℃，因此对应的输出为 3。第 4 天的温度是 36℃，后面没有更高的温度，它对应的输出是 0。其他的以此类推。

分析：

解决这个问题的直观方法很多人很快就能想到。对于数组中的每个温度，可以扫描它后面的温度直到发现一个更高的温度为止。如果数组包含 n 天的温度，那么这种思路的时间复杂度是 O(n^2)。

下面通过一个具体的例子来分析这个问题的规律。假设输入的表示每天的温度的数组为 [35, 31, 33, 36, 34]。第 1 天的温度是 35℃，此时还不知道后面会不会有更高的温度，所以先将它保存到一个数据容器中。第 2 天的温度是 31℃，比第 1 天温度低，同样也保存到数据容器中。第 3 天的温度是 33℃，比第 2 天的温度高，由此可知，第 2 天需要等 1 天才有更高的温度。

每次从数组中读取某一天的温度，并且都将其与之前的温度（也就是已经保存在数据容器中的温度）相比较。从离它较近的温度开始比较看起来是一个不错的选择，也就是后存入数据容器中的温度先拿来比较，这契合 "后进先出" 的特性，所以可以考虑用栈来实现这个数据容器。同时，需要计算出现更高温度的等待天数，存入栈中的数据应该是温度在数组中的下标。等待的天数就是两个温度在数组中的下标之差。

因此，处理到第 3 天的温度时，栈的状态为 [0, 1]。在知道第 2 天需要等 1 天将出现更高的温度之后，它就没有必要再保存在栈中，将它出栈。第 3 天的温度也需要入栈，以便和以后的温度比较，此时栈的状态为 [0, 2]。

第 4 天的温度是 36℃。从栈顶开始与之前的温度比较，它比第 3 天的温度 33℃ 高，因此第 3 天需要等 1 天就会出现更高的温度，这一天在数组中的下标 2 出栈。它也比第 1 天的温度 35℃ 高，因此第 1 天需要等 3 天才会出现更高的温度，这一天在数组中的下标 0 出现。然后将第 4 天在数组中的下标 3 入栈，以便和以后的温度比较。此时栈的状态为 [3]。最后一天的温度是 34℃，比位于栈顶的第 4 天的温度低，将其入栈，最终栈的状态是 [3, 4]。最终留在栈中的两天的后面都没有出现更高的温度。

解决这个问题的思路总结起来就是用一个栈保存每天的温度在数组中的下标。每次从数组中读取一个温度，然后将其与栈中保存的温度（根据下标可以得到温度）进行比较。如果当前温度比位于栈顶的温度高，那么就能知道位于栈顶那一天需要等待几天才会出现更高的温度。然后出栈 1 次，将当前温度与下一个位于栈顶的温度进行比较。如果栈中已经没有比当前温度低的温度，则将当前温度在数组中的下标入栈。

代码实现：

class Solution {
public:vector<int> dailyTemperatures(vector<int>& temperatures) {int n = temperatures.size();vector<int> result(n, 0);stack<int> st;for (int i = 0; i < n; ++i){while (!st.empty() && temperatures[i] > temperatures[st.top()]){result[st.top()] = i - st.top();st.pop();}
​st.push(i);}return result;}
};

保存在栈中的温度（通过数组下标可以得到温度）是递减排序的。这是因为如果当前温度比位于栈顶的温度高，位于栈顶的温度将出栈，所以每次入栈时当前温度一定比位于栈顶的温度低或相同。

假设输入数组的长度为 n。虽然上述代码中有一个嵌套的二重循环，但它的时间复杂度是 O(n)，这是因为数组中每个温度入栈、出栈各 1 次。这种解法的空间复杂度也是 O(n)。

面试题 39 : 直方图最大矩形面积

题目：

直方图是由排列在同一基线上的相邻柱子组成的图形。输入一个由非负数组成的数组，数组中的数字是直方图中柱子的高。求直方图中最大矩形面积。假设直方图中柱子的宽都为 1。例如，输入数组 [3, 2, 5, 4, 6, 1, 4, 2]，其对应的直方图如下图所示，该直方图中最大矩形面积为 12，如阴影部分所示。

分析：

矩形的面积等于宽乘以高，因此只要能确定每个矩形的宽和高，就能计算它的面积。如果直方图中一个矩形从下标为 i 的柱子开始，到下标为 j 的柱子结束，那么这两根柱子之间的矩形（含两端的柱子）的宽是 j - i + 1。矩形的高就是两根柱子之间的所有柱子最矮的高度。例如，上图中从下标为 2 的柱子到下标为 4 的柱子之间的矩形宽度是 3，矩形的高度最多只能是 4，即它们之间 3 根柱子最矮的高度。

方法一、暴力求解

如果能逐一找出直方图中所有的矩形并比较它们的面积，就能得到最大矩形面积。下面使用嵌套的二重循环遍历所有矩形，并比较它们的面积。

class Solution {
public:int largestRectangleArea(vector<int>& heights) {int maxArea = 0;for (int i = 0; i < heights.size(); ++i){int minHeight = heights[i];for (int j = i; j < heights.size(); ++j){if (heights[j] < minHeight)minHeight = heights[j];int area = minHeight * (j - i + 1);
​if (area > maxArea)maxArea = area;}}return maxArea;}
};

这种解法的时间复杂度是 O(n^2)，空间复杂度是 O(1)。

方法二、递归求解

上图的直方图中最矮的柱子在数组中的下标是 5，它的高度是 1。这个直方图的最大矩形有以下 3 种可能：

  1. 第 1 种是矩形通过这根最矮的柱子。通过最矮的柱子的最大矩形的高度是 1，宽度是 7。

  2. 第 2 种是矩形的起始柱子和终止柱子都在最矮的柱子的左侧，也就是从下标为 0 的柱子到下标为 4 的柱子的直方图的最大矩形。

  3. 第 3 种是矩形的起始柱子和终止柱子都在最矮的柱子的右侧，也就是从下标为 6 的柱子到下标为 7 的柱子的直方图的最大矩形。

第 2 种和第 3 种本质上来说和求整个直方图的最大矩形面积是同一个问题，可以调用递归函数解决。

class Solution {
private:int _largestRectangleArea(vector<int>& heights, int left, int right){if (left > right)return 0;if (left == right)return heights[left];
​int minHeightIndex = left;for (int i = left + 1; i <= right; ++i){if (heights[i] < heights[minHeightIndex])minHeightIndex = i;}int maxArea = heights[minHeightIndex] * (right - left + 1);int area1 = _largestRectangleArea(heights, left, minHeightIndex - 1);int area2 = _largestRectangleArea(heights, minHeightIndex + 1, right);if (area1 > maxArea)maxArea = area1;if (area2 > maxArea)maxArea = area2;return maxArea;}
​
public:int largestRectangleArea(vector<int>& heights) {return _largestRectangleArea(heights, 0, heights.size() - 1);}
};

假设输入数组的长度为 n。如果每次都能将 n 根柱子分成两根柱子数量为 n / 2 的子直方图，那么递归调用的深度为 O(logn)，整个递归算法的时间复杂度是 O(nlogn)。但如果直方图中柱子的高度是排序的（递增排序或递减排序），那么每次最矮的柱子都位于直方图的一侧，递归调用的深度就是 O(n)，此时递归算法的时间复杂度也变成 O(n^2)。

递归算法的空间复杂度取决于调用栈的深度，因此平均空间复杂度是 O(logn)，最坏情况下的空间复杂度是 O(n)。

方法三、单调栈法

计算以每根柱子为顶的最大矩形面积，比较这些矩形面积就能得到直方图中的最大矩形面积。

以某根柱子为顶的最大矩形，一定是从该柱子向两侧延伸直到遇到比它矮的柱子，这个最大矩形的高就是该柱子的高，最大矩形的宽是两侧比它矮的柱子中间的间隔。例如，为了求上图所示的直方图中以下标为 3 的柱子为顶的最大矩形面积，应该从该柱子开始向两侧延伸，左侧比它矮的柱子的下标是 1，右侧比它矮的柱子的下标是 5。因此，以下标为 3 的柱子为顶的最大矩形的高为 4，宽为 3（左右两侧比它矮的柱子的下标之差再减 1，即 5 - 1 - 1）。

class Solution {
public:int largestRectangleArea(vector<int>& heights) {int n = heights.size();vector<int> left(n, -1);vector<int> right(n, n);
​stack<int> st;for (int i = n - 1; i >= 0; --i){while (!st.empty() && heights[i] < heights[st.top()]){left[st.top()] = i;st.pop();}st.push(i);}st = stack<int>();for (int i = 0; i < n; ++i){while (!st.empty() && heights[i] < heights[st.top()]){right[st.top()] = i;st.pop();}st.push(i);}
​int maxArea = 0;for (int i = 0; i < n; ++i){int area = heights[i] * (right[i] - left[i] - 1);if (area > maxArea)maxArea = area;}return maxArea;} 
};

这种解法的时间复杂度是 O(n)，空间复杂度也是 O(n)。

 

面试题 40 : 矩阵中的最大矩形

题目：

请在一个由 0、1 组成的矩阵中找出最大的只包含 1 的矩形并输出它的面积。例如，在下图的矩阵中，最大的只包含 1 的矩形如阴影部分所示，它的面积是 6。

分析：

面试题 2.4 是关于最大矩形的，这个题目还是关于最大矩形的，它们之间有没有某种联系？如果能从矩阵中找出直方图，那么就能通过计算直方图中的最大矩形面积来计算矩阵中的最大矩形面积。

直方图是由排列在同一基线上的相邻柱子组成的图形。由于题目要求矩形中只包含数字 1，因此将矩阵中上下相邻的值为 1 的格子看成直方图中的柱子。如果分别以上图中的矩阵的每行为基线，就可以得到 4 个由数字 1 的格子组成的直方图，如下图所示。

在将矩阵转换成多个直方图之后，就可以计算并比较每个直方图的最大矩形面积，所有直方图中的最大矩形就是整个矩阵中的最大矩形。

代码实现：

class Solution {
private:int largestRectangleArea(vector<int>& heights) {int n = heights.size();vector<int> left(n, -1);vector<int> right(n, n);
​stack<int> st;for (int i = n - 1; i >= 0; --i){while (!st.empty() && heights[i] < heights[st.top()]){left[st.top()] = i;st.pop();}st.push(i);}st = stack<int>();for (int i = 0; i < n; ++i){while (!st.empty() && heights[i] < heights[st.top()]){right[st.top()] = i;st.pop();}st.push(i);}
​int maxArea = 0;for (int i = 0; i < n; ++i){int area = heights[i] * (right[i] - left[i] - 1);if (area > maxArea)maxArea = area;}return maxArea;}public:int maximalRectangle(vector<string>& matrix) {if (matrix.size() == 0 || matrix[0].size() == 0)return 0;
​int result = 0;vector<int> heights(matrix[0].size(), 0);for (int i = 0; i < matrix.size(); ++i){for (int j = 0; j < matrix[i].size(); ++j){if (matrix[i][j] == '0')heights[j] = 0;else++heights[j];}
​int maxArea = largestRectangleArea(heights);if (maxArea > result)result = maxArea;}return result;}
};

这篇关于《剑指 Offer》专项突破版 - 面试题 38、39 和 40 : 通过三道面试题详解单调栈（C++ 实现）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/698211。

相关文章

Spring Security基于数据库验证流程详解

Spring Security基于数据库验证流程详解

Spring Security 校验流程图 相关解释说明（认真看哦） AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证，则会调用 #attemptAuthentica
阅读更多...
hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu
阅读更多...
【C++ Primer Plus习题】13.4

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<
阅读更多...
C++包装器

C++包装器

包装器 在 C++ 中，“包装器”通常指的是一种设计模式或编程技巧，用于封装其他代码或对象，使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍，可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型： 1. 函数包装器 函数包装器用于封装一个或多个函数，使其接口更统一或更便于调用。例如，std::function 是一个通用的函数包装器，它可以存储任意可调用对象（函数、函数
阅读更多...
OpenHarmony鸿蒙开发（ Beta5.0）无感配网详解

OpenHarmony鸿蒙开发（ Beta5.0）无感配网详解

1、简介 无感配网是指在设备联网过程中无需输入热点相关账号信息，即可快速实现设备配网，是一种兼顾高效性、可靠性和安全性的配网方式。 2、配网原理 2.1 通信原理 手机和智能设备之间的信息传递，利用特有的NAN协议实现。利用手机和智能设备之间的WiFi 感知订阅、发布能力，实现了数字管家应用和设备之间的发现。在完成设备间的认证和响应后，即可发送相关配网数据。同时还支持与常规Sof
阅读更多...
C++11第三弹：lambda表达式 | 新的类功能 | 模板的可变参数

C++11第三弹：lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页： 南桥几晴秋 🌈C++专栏： 南桥谈C++ 🌈C语言专栏： C语言学习系列 🌈Linux学习专栏： 南桥谈Linux 🌈数据结构学习专栏： 数据结构杂谈 🌈数据库学习专栏： 南桥谈MySQL 🌈Qt学习专栏： 南桥谈Qt 🌈菜鸡代码练习： 练习随想记录 🌈git学习： 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�
阅读更多...
【C++】_list常用方法解析及模拟实现

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...
【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯，先赞后看哦~🎈🎈 🏆 作者简介：景天科技苑 🏆《头衔》：大厂架构师，华为云开发者社区专家博主，阿里云开发者社区专家博主，CSDN全栈领域优质创作者，掘金优秀博主，51CTO博客专家等。 🏆《博客》：Python全栈，前后端开发，小程序开发，人工智能，js逆向，App逆向，网络系统安全，数据分析，Django，fastapi
阅读更多...
让树莓派智能语音助手实现定时提醒功能

让树莓派智能语音助手实现定时提醒功能

最初的时候是想直接在rasa 的chatbot上实现，因为rasa本身是带有remindschedule模块的。不过经过一番折腾后，忽然发现，chatbot上实现的定时，语音助手不一定会有响应。因为，我目前语音助手的代码设置了长时间无应答会结束对话，这样一来，chatbot定时提醒的触发就不会被语音助手获悉。那怎么让语音助手也具有定时提醒功能呢？ 我最后选择的方法是用threading.Time
阅读更多...
Android实现任意版本设置默认的锁屏壁纸和桌面壁纸（两张壁纸可不一致）

Android实现任意版本设置默认的锁屏壁纸和桌面壁纸（两张壁纸可不一致）

客户有些需求需要设置默认壁纸和锁屏壁纸  在默认情况下 这两个壁纸是相同的  如果需要默认的锁屏壁纸和桌面壁纸不一样 需要额外修改 Android13实现 替换默认桌面壁纸： 将图片文件替换frameworks/base/core/res/res/drawable-nodpi/default_wallpaper.*  （注意不能是bmp格式） 替换默认锁屏壁纸： 将图片资源放入vendo
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2