# LeetCode 日記 #008: 334. Increasing Triplet Subsequence | 貪心算法 Greedy

> Given an integer array nums, return true if there exists a triple of indices (i, j, k) such that i < j < k and nums[i] < nums[j] < nums[k]. If no such indices exists, return false.

- **Example 1:**
Input: nums = [1,2,3,4,5]
Output: true
Explanation: Any triplet where i < j < k is valid.

- **Example 2:**
Input: nums = [5,4,3,2,1]
Output: false
Explanation: No triplet exists.

- **Example 3:**
Input: nums = [2,1,5,0,4,6]
Output: true
Explanation: nums[3] == 0 < nums[4] == 4 < nums[5] == 6.

### 題目概述

判斷題目給定的原始陣列中，是否存在連續三個元素是呈現遞增的子陣列，有的話返回 true，沒有則返回 false。要解決這題就必須學習一個新的算法思想與策略——**貪心算法 (Greedy)**。

## 貪心算法 (Greedy)

貪心算法的核心思想是，在每一步選擇中都採取當前狀態下最優的選擇（局部最優），期待最終能得到「全局最優」。

### 特性

* **局部最優選擇**：每一步的選擇都是當前看起來最好的，不考慮全局
* **無後效性**：當前的決策不會影響未來的決策
* **子問題最優性質**：問題的最優解包含子問題的最優解
* **簡單高效**：通常實現簡單且時間複雜度較低
* **不需要回溯**：一旦做出選擇，就不會回頭重新考慮

### 使用時機

* **問題可以分解為子問題**：整體問題可以分解為一系列子問題
* **滿足最優子結構**：問題的最優解包含子問題的最優解
* **具有貪心選擇性質**：每一步的局部最優選擇能導致全局最優解
* **子問題之間相互獨立**：一個子問題的解不會影響其他子問題

判斷問題是否適合使用貪心算法，可以考慮以下幾點：

* **「問題是否有明顯的局部最優選擇」**：例如「選擇當前最小/最大值」
* **「局部最優是否能推導出全局最優」**：需要證明局部選擇不會導致次優解
* **「問題是否具有無後效性」**：當前決策不會影響未來的決策空間
* **「問題是否具有貪心選擇性質」**：每一步的最優選擇能導致全局最優解

## 題解

第一眼看到這題時，可從以下幾個角度來分析是否適用貪心算法：

1. **問題結構**：
首先，觀察到這個問題的核心是尋找三個遞增的元素，而不是求所有可能的遞增子序列。這種「是否存在」的問題通常比「找出所有」的問題更適合使用貪心或者更簡單的算法。

2. **子問題與獨立性分析**：
當分析如何判斷陣列中是否存在遞增的三元組時，關鍵問題變成：
- 如何有效地記錄已經看到的最小值
- 如何記錄基於這個最小值的第二小值
- 如何判斷是否存在第三個值大於前兩個值

> 這種子問題結構表明可能不需要記住所有歷史信息，只需要記住關鍵狀態。

3. **最優子結構特性識別**：
如果已經找到當前最小值 first 和第二小值 second，那麼只要找到任何一個大於 second 的值，就能確定存在遞增三元組，這符合貪心算法的最優子結構特性 - 維護當前最優的 first 和 second 有助於找到全局解。

4. **局部最優選擇分析**：
考慮在迭代時的每一步決策，如果遇到一個更小的值，更新 first 是局部最優的（讓後續找到合適的 second 和第三個值的可能性更大）如果遇到一個介於 first 和 second 之間的值，更新 second 是局部最優的，如果遇到一個大於 second 的值，我們直接找到了答案。這種每一步的局部最優選擇，能夠指向全局最優解，是貪心算法的核心特徵。

5. **無後效性判斷**：
當我更新 first 或 second 時，我不需要考慮它們之前的值或相對位置，只關心數值大小關係。這種特性表明問題具有無後效性，適合使用貪心算法。

class Solution {
    public boolean increasingTriplet(int[] nums) {
        int first = Integer.MAX_VALUE;
        int second = Integer.MAX_VALUE;

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > second) {
                return true;
            } else if (nums[i] > first && nums[i] < second) {
                second = nums[i];
            } else if (nums[i] < first) {
                first = nums[i];
            }
        }
        return false;
    }
}

### 總結
綜合以上分析，當看到這類「尋找特定模式」且只需要「是/否」答案的問題時，可優先考慮是否適用貪心算法。特別是當問題可以通過維護少量關鍵變量（如 first 和 second）來表達狀態，並且每一步都有明確的局部最優選擇時。如果使用貪心策略，整個算法只需要 O(n) 的時間複雜度和 O(1) 的空間複雜度，非常高效。貪心算法通常比動態規劃或回溯算法更簡潔高效。