專欄：50多種數據結構徹底征服

專欄：50多種經典圖論算法全部掌握

最近一網友在面試騰訊的時候掛了，原因是面試官說他太松弛了，沒有目標感，沒有表示強烈的求知欲，網友評論說：太松弛了，跑的概率比較大。

太松弛，不內卷，不內耗，我覺得挺好的，這些反而成為了求職的缺點。實際上真誠應該是求職者最優秀的品質，可是在職場中卻不受歡迎，大家總是喜歡一些拍馬溜須，阿諛奉承的好話。

記得十多年前有一次我實習找工作的時候，我的回答讓hr一愣一愣的，因為我所有的回復全部出乎她意料之外。后來發現這樣不行，又上網查了各種話術，什么上進心，責任心，只要是好的詞都全部往上堆。

面試中我最怕問到的一個問題就是你的優點是什么，缺點是什么？如果我直言不諱，和盤托出，他們肯定不會要我，所以只能昧著良心說一些無關痛癢的話。

--------------下面是今天的算法題--------------

來看下今天的算法題，這題是LeetCode的第1441題：用棧操作構建數組，難度是中等。

給你一個數組 target 和一個整數 n。每次迭代，需要從 list = { 1 , 2 , 3 ..., n } 中依次讀取一個數字。請使用下述操作來構建目標數組 target ：

1，"Push"：從 list 中讀取一個新元素， 并將其推入數組中。

2，"Pop"：刪除數組中的最后一個元素。

3，如果目標數組構建完成，就停止讀取更多元素。

題目數據保證目標數組嚴格遞增，并且只包含 1 到 n 之間的數字。請返回構建目標數組所用的操作序列。如果存在多個可行方案，返回任一即可。

示例1：

輸入：target = [1,3], n = 3 輸出：["Push","Push","Pop","Push"] 解釋： 讀取 1 并自動推入數組 -> [1] 讀取 2 并自動推入數組，然后刪除它 -> [1] 讀取 3 并自動推入數組 -> [1,3]

示例2：

輸入：target = [1,2], n = 4 輸出：["Push","Push"] 解釋：只需要讀取前 2 個數字就可以停止。

• 1 <= target.length <= 100

• 1 <= n <= 100

• 1 <= target[i] <= n

• target 嚴格遞增

問題分析

這題說的是從 1 到 n 依次讀取數字，然后構建target數組，讀取的時候如果不是數組中的數字，要把它刪除掉（pop）。

這題我們不需要使用用一個棧，直接模擬即可，因為數組中的元素都是遞增的，所以在數組中相鄰的兩個數字之間的數字我們可以一邊添加（push）一邊刪除（pop），比如數組[3,7]，在 3 和 7 之間的數字 4,5,6 不可能是數組中的數字，所以添加完之后還要把它給刪除。

JAVA：

public List   buildArray(int[] target, int n) {     List ans =  new ArrayList<>();     int last = 0;     for (int num : target) {         // 上一個數字到當前數字之間要push和pop。         for (int i = last + 1; i < num; i++) {             ans.add("Push");             ans.add("Pop");         }         ans.add("Push");// 當前數字push         last = num;     }     return ans; }

C++：

public:     vector

  buildArray(vector

 &target, int n) {         vector

 ans;         int last = 0;         for (int num: target) {             // 上一個數字到當前數字之間要push和pop。             for (int i = last + 1; i < num; i++) {                 ans.emplace_back("Push");                 ans.emplace_back("Pop");             }             ans.emplace_back("Push");// 當前數字push             last = num;         }         return ans;     }

筆者簡介

博哥，真名：王一博，畢業十多年， 作者，專注于 數據結構和算法 的講解，在全球30多個算法網站中累計做題2000多道，在公眾號中寫算法題解800多題，對算法題有自己獨特的解題思路和解題技巧，喜歡的可以給個關注，也可以 下載我整理的1000多頁的PDF算法文檔 。