介紹

總而言之是時候利用暑假鍛煉一下算法技術(shù)，一提算法面試就面露難色的情形總不能一直持續(xù)下去。本欄目面向有一定基礎(chǔ)的編程愛好者，每天（如果up不鴿）分享并解析一道LeetCode中高難度題目（通常是hard）。有興趣的小伙伴可以一起跟著做并且討論解法。目前的教材是花花醬的Leetcode Problem List【1】.

適合人群：

有一定算法基礎(chǔ)，但是還未能順利通過筆試/面試，總覺得算法題目想不明白的你。

不適合人群：

算法入門級選手（一上來就做難題可能并不合適，建議首先專注簡單/中等題目）

非常不適合人群：

算法競賽選手（這種小兒科的問題完全是在浪費您的時間）

過往題目在這里！

子數(shù)組的最小值之和

題目看這里，leetcode第九零七題，medium難度：
https://leetcode.com/problems/sum-of-subarray-minimums/

強(qiáng)烈建議讀者自己先做（不過真的會有讀者嗎，笑），有任何問題歡迎在評論區(qū)討論，up看到了會及時回復(fù)。做完了歡迎在評論區(qū)打卡～

解析

解法一

本題雖然難度是medium，但是那應(yīng)該是指的O(n^2)難度的解法。對于O(n)難度，我個人認(rèn)為是毫無疑問的hard難度?，F(xiàn)在我們先來看一個相對直觀和易于理解的暴力解法。對于數(shù)組中的每一個新元素，我們都從這個元素的位置開始向數(shù)組的開頭方向遍歷，同時維護(hù)一個“當(dāng)前最小值”。在這個向數(shù)組頭部方向移動的窗口中，最小值可能會被更新，每次更新后的最小值都被加入到最終的結(jié)果中。

解法二

接下來的才是重頭戲！花了一個多小時，真的是不好想。容我把自己的思路走一遍：

首先，我們需要明確一點，對于數(shù)組中的任意位置i，我們會向數(shù)組的開頭方向進(jìn)行遍歷。在考慮的過程中，我們需要進(jìn)行分情況討論，同時忽略那些不重要的邊界情況。

有兩種可能的情況。假設(shè)我們當(dāng)前正在遍歷到位置j（注意，這里j<i），那么元素a[j]要么小于a[i]，要么大于a[i]。對于a[j]等于a[i]的情況，我們先不考慮。

如果a[j]小于a[i]，那么在從j到i的子數(shù)組a[j:i+1]中，a[j]可能是最小值，此時最小值與a[i]無關(guān)。

如果a[j]大于a[i]，那么在從j到i的子數(shù)組a[j:i+1]中，a[i]可能是最小值，當(dāng)然，也可能不是。

現(xiàn)在，我們再來思考一下解法一的過程。每一步我們都會從i開始向前遍歷，比較元素的大小。如果遇到了一個元素a[j]小于a[i]，那么在j位置之后，子數(shù)組的最小值就與a[i]的值沒有關(guān)系。如果a[j]始終大于等于a[i]，那么子數(shù)組的最小值始終是a[i]。（這是非常重要的一點，請讀者務(wù)必確認(rèn)已經(jīng)理解）

理解了這一點后，這個問題就可以轉(zhuǎn)化為在已知位置i的情況下，找到i之前第一個比a[i]小的值的位置。這是單調(diào)棧經(jīng)典問題的一種，只有熟悉這類問題的人才能快速看出。對于不熟悉的同學(xué)，建議你從LeetCode的739題開始學(xué)習(xí)。所以說，難題做不出來，很可能是題目量還沒夠，和智商恐怕關(guān)系不大。

一旦我們找到了第一個比a[i]小的值的位置k，那么在k到i的范圍內(nèi)，最小值始終為a[i]，我們只需要將(i-k)*a[i]加入到結(jié)果中。但是在k之前的部分呢？我們需要像處理i一樣重新計算嗎？

這里的重復(fù)結(jié)構(gòu)或許讓你想到了動態(tài)規(guī)劃。我們可以預(yù)先計算好k之前的部分，并存儲起來，等到需要使用時直接取用即可。

這個問題很好地展示了如何結(jié)合使用單調(diào)棧和動態(tài)規(guī)劃的思想，值得一個難題的評價。比起腦筋急轉(zhuǎn)彎類的難題，此類難題是最值得一做的，因為可以同時鍛煉多個解題技巧。

思考樂園

如果讀者想明白了解法二，想必大腦已經(jīng)過載。所以今天就沒有思考題目。不過歡迎把任何問題寫在評論區(qū)。

音樂推薦

今天的題目真是讓人感慨良深。從最初的“這啥呀”到最后透徹的搞清楚解法，其中相隔的就是思考的過程?？偠灾菚r候來到我們慣例的推薦環(huán)節(jié)，來自ttup三人的舞蹈Catallena送給今天也勇于挑戰(zhàn)難題的你，其實人家跳的還挺好看的。不過ttup不是四個人嗎？為什么只有三人跳舞？這下四減一了

教材鏈接

【1】https://zxi.mytechroad.com/blog/leetcode-problem-categories/