介绍

总而言之是时候利用暑假锻炼一下算法技术，一提算法面试就面露难色的情形总不能一直持续下去。本栏目面向有一定基础的编程爱好者，每天（如果up不鸽）分享并解析一道LeetCode中高难度题目（通常是hard）。有兴趣的小伙伴可以一起跟着做并且讨论解法。目前的教材是花花酱的Leetcode Problem List【1】.

(资料图片)

适合人群：

有一定算法基础，但是还未能顺利通过笔试/面试，总觉得算法题目想不明白的你。

不适合人群：

算法入门级选手（一上来就做难题可能并不合适，建议首先专注简单/中等题目）

非常不适合人群：

算法竞赛选手（这种小儿科的问题完全是在浪费您的时间）

过往题目在这里！

子数组的最小值之和

题目看这里，leetcode第九零七题，medium难度：/problems/sum-of-subarray-minimums/

强烈建议读者自己先做（不过真的会有读者吗，笑），有任何问题欢迎在评论区讨论，up看到了会及时回复。做完了欢迎在评论区打卡～

解析

解法一

本题虽然难度是medium，但是那应该是指的O(n^2)难度的解法。对于O(n)难度，我个人认为是毫无疑问的hard难度。现在我们先来看一个相对直观和易于理解的暴力解法。对于数组中的每一个新元素，我们都从这个元素的位置开始向数组的开头方向遍历，同时维护一个“当前最小值”。在这个向数组头部方向移动的窗口中，最小值可能会被更新，每次更新后的最小值都被加入到最终的结果中。

解法二

接下来的才是重头戏！花了一个多小时，真的是不好想。容我把自己的思路走一遍：

首先，我们需要明确一点，对于数组中的任意位置i，我们会向数组的开头方向进行遍历。在考虑的过程中，我们需要进行分情况讨论，同时忽略那些不重要的边界情况。

有两种可能的情况。假设我们当前正在遍历到位置j（注意，这里j<i），那么元素a[j]要么小于a[i]，要么大于a[i]。对于a[j]等于a[i]的情况，我们先不考虑。

如果a[j]小于a[i]，那么在从j到i的子数组a[j:i+1]中，a[j]可能是最小值，此时最小值与a[i]无关。

如果a[j]大于a[i]，那么在从j到i的子数组a[j:i+1]中，a[i]可能是最小值，当然，也可能不是。

现在，我们再来思考一下解法一的过程。每一步我们都会从i开始向前遍历，比较元素的大小。如果遇到了一个元素a[j]小于a[i]，那么在j位置之后，子数组的最小值就与a[i]的值没有关系。如果a[j]始终大于等于a[i]，那么子数组的最小值始终是a[i]。（这是非常重要的一点，请读者务必确认已经理解）

理解了这一点后，这个问题就可以转化为在已知位置i的情况下，找到i之前第一个比a[i]小的值的位置。这是单调栈经典问题的一种，只有熟悉这类问题的人才能快速看出。对于不熟悉的同学，建议你从LeetCode的739题开始学习。所以说，难题做不出来，很可能是题目量还没够，和智商恐怕关系不大。

一旦我们找到了第一个比a[i]小的值的位置k，那么在k到i的范围内，最小值始终为a[i]，我们只需要将(i-k)*a[i]加入到结果中。但是在k之前的部分呢？我们需要像处理i一样重新计算吗？

这里的重复结构或许让你想到了动态规划。我们可以预先计算好k之前的部分，并存储起来，等到需要使用时直接取用即可。

这个问题很好地展示了如何结合使用单调栈和动态规划的思想，值得一个难题的评价。比起脑筋急转弯类的难题，此类难题是最值得一做的，因为可以同时锻炼多个解题技巧。

思考乐园

如果读者想明白了解法二，想必大脑已经过载。所以今天就没有思考题目。不过欢迎把任何问题写在评论区。

音乐推荐

今天的题目真是让人感慨良深。从最初的“这啥呀”到最后透彻的搞清楚解法，其中相隔的就是思考的过程。总而言之是时候来到我们惯例的推荐环节，来自ttup三人的舞蹈Catallena送给今天也勇于挑战难题的你，其实人家跳的还挺好看的。不过ttup不是四个人吗？为什么只有三人跳舞？这下四减一了

教材链接

【1】/blog/leetcode-problem-categories/

关键词：