[1,8,6,2,5,4,8,3,7]
1. sliding window >> 不可行 找不到最佳解
2. 暴力


1 * 3 = 3 (0,3)
O(n! / 2)
---
## Greedy 2 <= n <= 10^5

[1,8,6,2,5,4,8,3,7]
1. (1,n.size()-1) >> 1,7 ==> min(n[0],n[8]) * n.size() - 1
2. water << min(n[0],n[8]) * n.size() - 1
3. min(a,b) a 往內推 變大 >> 更新
4. min(a,b) b 往內通 變大 >> 更新

class Solution {
public:
    int maxArea(vector<int>& height) {
        int water = 0;
        int left = 0;
        int right = height.size()-1;
        // sliding window algorithm
        while(left<right){
            int h = min(height[left],height[right]);
            water = max(water,(right-left) * h);
            while(height[left] <= h && left < right) left++;
            while(height[right]<= h && left < right) right--;
        }
        return water;
    }
};

### h = min(height[left],height[right]) 紀錄上一次最佳
[1,1,1,1,18,1,1,1,1,1,1,1]
optimize substructure >>

# [Decode ways](https://leetcode.com/problems/decode-ways/)

'A' -> "1"
'B' -> "2"
...
'Z' -> "26"

input : 數字字串 包含 0-9

1234
1 2 3 4 > ABCD
12 3 4 > LCD
1 23 4 > A W D

1. 不能解的方法 (OBST)

O(n^2)

1 2 3 4
1 1 1 1
 2 2 1
  3 2
   3
0 > 不能當頭
1010 >> 不能出現
10 10
rule based > 直接排除

1234
取 1 '234'
取 12 '34'

走一'1 11111111111'
走二'11 1111111111'
只能走 1,2

T(n) = T(n-1) + T(n-2)
T(0,1) = 1

10 10 10

[1,1,1,1,1,1]

class Solution {
public:
    int numDecodings(string s) {
        if (s.empty() || s[0] == '0') return 0;
        vector<int> dp(s.size() + 1, 0);
        dp[0] = 1;
        for (int i = 1; i < dp.size(); ++i) {
            if (s[i - 1] != '0') dp[i] += dp[i - 1];
            if (i >= 2 && s.substr(i - 2, 2) <= "26" && s.substr(i - 2, 2) >= "10") {
                dp[i] += dp[i - 2];
            }
        }
        return dp.back();
    }
};