九章演算法 | Twitter 面試題：The Previous Number

來自專欄九章演算法 - LintCode領扣 題解6 人贊了文章

撰文 | JZ

專欄 | 九章演算法

題目描述

給一個數組，對於每一個元素，找出它之前第一個比它小的元素的值。如果沒有，則輸出它本身。

思路點撥

維護一個單調遞增的棧。對於元素i，判斷棧頂是否滿足條件，如果不滿足，說明對於後面的元素j，i比棧頂更優。所以彈出棧頂，直到棧為空。然後把元素i放入棧中。複雜度O(n)。

考點分析

本題考查的是單調棧，滿足條件的答案顯然是滿足單調性的，所以可以用一個棧來維護這個單調性，就可以O(n)解決問題了。

九章參考程序

http://www.jiuzhang.com/solution/the-previous-number/

/*** 本參考程序來自九章演算法，由 @斌助教 提供。版權所有，轉發請註明出處。* - 九章演算法致力於幫助更多中國人找到好的工作，教師團隊均來自矽谷和國內的一線大公司在職工程師。* - 現有的面試培訓課程包括：九章演算法班，系統設計班，演算法強化班，Java入門與基礎演算法班，Android 項目實戰班，* - Big Data 項目實戰班，演算法面試高頻題班, 動態規劃專題班* - 更多詳情請見官方網站：http://www.jiuzhang.com/?source=code*/ public class Solution { /** * @param num: The arry you should handle * @return: Return the array */ public int[] getPreviousNumber(int[] num) { // Write your code here int[] stack = new int[num.length]; int[] ans = new int[num.length]; int top = -1; for(int i = 0; i < num.length; i++) { while(top != -1 && num[i] <= stack[top]) { top --; } stack[++top] = num[i]; if(top > 0) { ans[i] = stack[top - 1]; } else { ans[i] = num[i]; } } return ans; }}

推薦閱讀：