剑指Offer（数据结构与算法面试题精讲）C++版——day12

题目一：小行星碰撞

    题目：输入一个表示小行星的数组，数组中每个数字的绝对值表示小行星的大小，数字的正负号表示小行星运动的方向，正号表示向右飞行，负号表示向左飞行。如果两颗小行星相撞，那么体积较小的小行星将会爆炸最终消失，体积较大的小行星不受影响。如果相撞的两颗小行星大小相同，那么它们都会爆炸消失。飞行方向相同的小行星永远不会相撞。求最终剩下的小行星。例如，有6颗小行星[4, 5, -6, 4, 8, -5]，如图6.2所示（箭头表示飞行的方向），它们相撞之后最终剩下3颗小行星[-6, 4, 8]。

    由题意可知，这里我们可使用栈来实现，依次检查每个小行星的运动方向以及小行星大小，比如，这里拿[+4,+5,-6]三颗行星举例，由于-6的小行星比+4和+5行星大，那么由于-6行星和+4、+5两个行星一定会相撞，最后只剩下-6行星。如果使用栈结构来存储就能够很好的解决这个问题，一开始+4直接压入到栈中，然后遇到了+5由于不存在反向，于是同样压入栈中，遇到-6（待入栈元素）之后，由于与栈顶元素方向不一致，弹出栈顶元素，比较，发现栈顶元素应该被销毁，于是接着弹出直到这个待入栈元素要么消失，要么入栈，或者栈为空。通过这样的分析可以得到如下代码：

int getDirection(int number) {return number > 0 ? 1 : -1;
}
vector<int> getRemain(vector<int> arr) {stack<int> st;int top=0;for(int i=0,size=arr.size(); i<size; ++i) {if(st.empty()) {st.push(arr[i]);continue;} else {top=st.top();if(getDirection(top)==1&&getDirection(arr[i])==-1) {if(abs(top)>abs(arr[i])) {continue;} else if(arr[i]==top) {st.pop();} else {while(!st.empty()&&abs(top)<abs(arr[i])) {st.pop();if(st.empty()) {break;} else {top=st.top();}}if(st.empty()) {st.push(arr[i]);} else if(top==arr[i]) {st.pop();}}} else {st.push(arr[i]);}}}vector<int> result= {};while(!st.empty()) {result.push_back(st.top());st.pop();}return result;
}

题目二：每日温度

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

    这里存在一个关键问题，对于前面出现过的数据，无法知道后面还有几个数，无法判断距离更大气温的天数，比如[4,3,2,1,6]，只有等到所有的数都获取之后才知道最终确认距离更高气温的天数。如果是使用暴力法，那么对于第i个数，最坏情况下需要遍历其后的(n-i)个数，这样最坏的时间复杂度为O(n^2)。
    分析可以发现，对于示例数组[35,31,33,36,34]，可以利用栈结构保存暂时没有确认距离更大的元素的下标，比如这里从左到右遍历，最开始遍历[35,31]都没有出现过更高气温，所以压入到栈中[0,1]，接下来遍历到新元素[33]，可以从栈取出栈顶元素判断，发现找到了一个更大的，用当前新来的元素的下标减去栈中元素的下标即可得到距离更大元素的下标。按照这样的方式就能够一次遍历拿到所有元素距离更大元素的个数了，最终得到代码如下：

vector<int> getRemainDays(vector<int> arr) {stack<int> st;int size=arr.size(),top=0;vector<int> result(size,0);for(int i=0; i<size; ++i) {if(st.empty()||arr[st.top()]>=arr[i]) {st.push(i);} else {top=st.top();while(arr[top]<arr[i]) {result[top]=i-top;st.pop();if(st.empty()) {break;} else {top=st.top();}}}}return result;
}

    这题得思路比较巧妙，很值得积累。利用了栈去保留前面没有被计算出结果，然后再利用栈得特性在之后得运算中弹出栈中元素，利用已知数据推理出结果。这里得时间复杂度为O(n)，因为在最坏情况下每个元素入栈一次，出栈一次。

题目三：直方图最大矩形面积

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

    这道题似曾相识，应该也是leetcode上面的题目。这题如果先不考虑使用栈相关的数据结构，使用前面提到的双指针法是否可行呢，设置前后指针，一开始让前后两指针都指向第一个数，然后第一个数后移，移到一定程度之后前指针也后移。分析发现这个方法是不行的，因为前一个指针往前移的过程中可能矩形会缩小，不满足双指针适用条件。
    这样不行那蛮力法呢，显然是可行的，双重遍历数组进行组合定界，比如锁定一组下标[min,max]，然后矩形的面积就等于(max-min)*min{arr[min-max]}，但是这样的事件复杂度太高了。
    其实，这里有一个更加巧妙的方法——单调栈法。分析发现，对于每个矩形面积的计算，可以以当前扫描到的柱子作为基准，然后向该柱子左右两次查找比基准柱子矮的柱子，比如以下标为3的坐标为例（也就是数组中第一次出现的4），扫描两侧可以发现左侧更矮的柱子下标为1（也就是数组中第一次数显的2），右侧更矮的柱子下标为5（也就是数组中的1），从而可以得到以数值4为基准的最大矩形面积为4*(5-1-1)=12。
    受到这一点的启发，我们可以得到一个非常巧妙的方法，现在的关键就在于为每个矩形左右两侧更矮的柱子定界，和前面题目2的方法类似，我们从左到右遍历数组（也就是这里矩形柱），构建一个柱子高度严格递增的矩形柱栈（为了方便获取柱子的高度和计算矩形宽度，这里和题目2一致存储下标），如果当前遍历的柱子比栈顶已有的柱子矮，那么说明当前栈顶柱子的左右下界都找到了，那么可以根据定界计算其最大矩形面积。如果当前遍历的柱子的高度比当前栈顶的柱子的高度高，那么直接入栈（以存储下标的形式）。最终得到如下代码：

int getMaxRectSquare(vector<int> arr) {stack<int> st;int result=0,size=arr.size(),top=0,height=0,width=0;for(int i=0; i<size; ++i) {while(!st.empty()&&arr[st.top()]>=arr[i]) {//构建一个严格递增的单调栈 height=arr[st.top()];st.pop();width=st.empty() ? i:(i-st.top()-1);if(width*height>result) {result=width*height;}}st.push(i);}while(!st.empty()) {top=st.top();height=arr[top];st.pop();width=st.empty()?arr.size():(arr.size()-st.top()-1);//左侧元素边界，否则取所有 if(width*height>result) {result=width*height;}}return result;
}

附录：源码gitee仓库

    考虑到有些算法需要模拟数据，如果全部放进来代码显得过长，不利于聚焦在算法的核心思路上。于是把所有的代码整理到了开源仓库上，如果想要看详细模拟数据，可在开源仓库自取：【凌空暗羽/剑指offer-C++版手写代码】。

    我是【Jerry说前后端】，本系列精心挑选的算法题目全部基于经典的《剑指 Offer（数据结构与算法面试题精讲）》。在如今竞争激烈的技术求职环境下，算法能力已成为前端开发岗位笔试考核的关键要点。通过深入钻研这一系列算法题，大家能够系统地积累算法知识和解题经验。每一道题目的分析与解答过程，都像是一把钥匙，为大家打开一扇通往高效编程思维的大门，帮助大家逐步提升自己在数据结构运用、算法设计与优化等方面的能力。
    无论是即将踏入职场的应届毕业生，还是想要进一步提升自己技术水平的在职开发者，掌握扎实的算法知识都是提升竞争力的有力武器。希望大家能跟随我的步伐，在这个系列中不断学习、不断进步，为即将到来的前端笔试做好充分准备，顺利拿下心仪的工作机会！快来订阅吧，让我们一起开启这段算法学习之旅！