一、題目描述

給你一個(gè)整數(shù)數(shù)組?nums?，數(shù)組中共有?n?個(gè)整數(shù)。132 模式的子序列?由三個(gè)整數(shù)?nums[i]、nums[j]?和?nums[k]?組成，并同時(shí)滿足：i < j < k?和?nums[i] < nums[k] < nums[j]?。

如果?nums?中存在?132 模式的子序列?，返回?true?；否則，返回?false?。

示例 1：

輸入：nums = [1,2,3,4]
輸出：false
解釋：序列中不存在 132 模式的子序列。

示例 2：

輸入：nums = [3,1,4,2]
輸出：true
解釋：序列中有 1 個(gè) 132 模式的子序列： [1, 4, 2] 。

示例 3：

輸入：nums = [-1,3,2,0]
輸出：true
解釋：序列中有 3 個(gè) 132 模式的的子序列：[-1, 3, 2]、[-1, 3, 0] 和 [-1, 2, 0] 。

提示：

• n == nums.length
• 1 <= n <= 2 * 10^5
• -10^9 <= nums[i] <= 10^9

二、解題思路

要解決這個(gè)問題，我們可以使用一個(gè)單調(diào)棧來幫助我們找到滿足132模式的子序列。以下是解題思路：

1. 從后向前遍歷數(shù)組，維護(hù)一個(gè)單調(diào)遞減棧，棧中存儲(chǔ)的是數(shù)組元素的索引。
2. 使用一個(gè)變量third來記錄當(dāng)前遍歷到的元素作為nums[k]時(shí)，所有可能的nums[i]中的最大值。
3. 當(dāng)遍歷到一個(gè)元素nums[j]時(shí)，如果third不為空且nums[j] > third，則說明找到了一個(gè)滿足條件的子序列，返回true。
4. 如果當(dāng)前元素nums[j]小于棧頂元素對(duì)應(yīng)的值，則將棧頂元素彈出，并更新third為彈出的元素值，因?yàn)榇藭r(shí)彈出的元素可以作為nums[k]，而nums[j]可以作為nums[j]，我們記錄下nums[k]中的最大值作為third。
5. 將當(dāng)前元素的索引壓入棧中。
6. 如果遍歷完數(shù)組仍未找到滿足條件的子序列，則返回false。

三、具體代碼

class Solution {public boolean find132pattern(int[] nums) {if (nums == null || nums.length < 3) {return false;}// 單調(diào)棧，存儲(chǔ)的是元素的索引Stack<Integer> stack = new Stack<>();// third變量記錄所有可能的nums[i]中的最大值int third = Integer.MIN_VALUE;// 從后向前遍歷數(shù)組for (int i = nums.length - 1; i >= 0; i--) {// 如果當(dāng)前元素小于third，說明找到了132模式if (nums[i] < third) {return true;}// 當(dāng)棧不為空且當(dāng)前元素大于棧頂元素時(shí)，更新thirdwhile (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {third = nums[stack.pop()];}// 將當(dāng)前元素的索引壓入棧中stack.push(i);}// 如果遍歷完數(shù)組仍未找到滿足條件的子序列，則返回falsereturn false;}
}

四、時(shí)間復(fù)雜度和空間復(fù)雜度

1. 時(shí)間復(fù)雜度

• 遍歷數(shù)組：我們使用了一個(gè)for循環(huán)來遍歷數(shù)組中的每個(gè)元素，這個(gè)操作的時(shí)間復(fù)雜度是O(n)，其中n是數(shù)組的長度。
• 棧操作：在每次遍歷中，每個(gè)元素最多只會(huì)被壓入棧一次，并且最多也只會(huì)被彈出一次。因此，整個(gè)數(shù)組遍歷過程中，每個(gè)元素最多只會(huì)經(jīng)過棧兩次（一次入棧，一次出棧），這意味著棧相關(guān)的操作的總時(shí)間復(fù)雜度也是O(n)。

由于這兩個(gè)操作是順序執(zhí)行的（遍歷數(shù)組和棧操作是同時(shí)進(jìn)行的），所以總的時(shí)間復(fù)雜度是O(n)。

2. 空間復(fù)雜度

• ?？臻g：在最壞的情況下，如果數(shù)組是單調(diào)遞增的，那么所有元素都會(huì)被壓入棧中。因此，棧的空間復(fù)雜度是O(n)，其中n是數(shù)組的長度。
• 輔助空間：除了棧之外，我們只使用了一個(gè)額外的變量third來存儲(chǔ)中間值，這個(gè)變量占用的空間是常數(shù)級(jí)的，即O(1)。

因此，總的空間復(fù)雜度是O(n)，由棧的大小決定。

五、總結(jié)知識(shí)點(diǎn)

• 數(shù)組遍歷：

  • 使用for循環(huán)從后向前遍歷數(shù)組，這是為了能夠利用棧來維護(hù)一個(gè)單調(diào)遞減的序列。

• 棧（Stack）的使用：

  • 使用Java的Stack類來存儲(chǔ)數(shù)組元素的索引，棧在這里用于維護(hù)一個(gè)單調(diào)遞減的序列，幫助我們找到可能的nums[k]。

• 條件判斷：

  • 使用if語句來判斷是否找到了132模式的子序列。
  • 使用while循環(huán)來處理?xiàng)Ｖ性?#xff0c;當(dāng)棧不為空且當(dāng)前元素大于棧頂元素時(shí)，更新third變量。

• 最小值初始化：

  • 使用Integer.MIN_VALUE來初始化third變量，確保在比較時(shí)能夠正確地更新third為更大的值。

• 棧的基本操作：

  • push()：將元素壓入棧中。
  • pop()：從棧中彈出元素。
  • peek()：查看棧頂元素而不彈出。

• 返回值：

  • 方法返回一個(gè)布爾值，表示是否找到了132模式的子序列。

• 邊界條件檢查：

  • 在方法開始時(shí)檢查輸入數(shù)組是否為空或長度小于3，因?yàn)橹辽傩枰?個(gè)元素才能形成132模式。

• 整數(shù)比較：

  • 在代碼中多次進(jìn)行了整數(shù)比較，這是基本的編程操作。

• 邏輯推理：

  • 整個(gè)算法的設(shè)計(jì)基于對(duì)132模式的理解，以及如何通過棧來維護(hù)一個(gè)潛在的有效序列，這是算法的核心。

以上就是解決這個(gè)問題的詳細(xì)步驟，希望能夠?yàn)楦魑惶峁﹩l(fā)和幫助。