首先是 334. Increasing Triplet Subsequence (medium)

給一個數列num，請找出是否存在三個索引值可以導致，num[i] < num[j] < num[k]。

一個想錯方向絕對寫不出來，想對方向簡單到爆炸的好題目。想當初我就是想錯方向卡了一下。

想法：
1.從小的數字開始找，因為串列會從左往右迭代，如果找到一個比較小的數字，直接存下即可。(若從大的數字開始找就必須反過來寫)
2.因為小的必定在最後面，如果往後找得比最小的大，就可以放在j

class Solution:
    #i,j,k不用連結在一起
    #從小的開始找
    #因為小的必定在最後面，如果往後找得比最小的大，就可以放在j
    #如果比j大就是k，就結束了
    def increasingTriplet(self, nums: List[int]) -> bool:
        i,j = float('inf'),float('inf')
        for n in nums:
            if n <= i:
                i = n
            elif n <= j:
                j = n
            else:
                return 1
        return 0
    
    #這寫法比較難解釋
    def increasingTriplet(self, nums: List[int]) -> bool:
        j,k = -float('inf'),-float('inf')
        for n in nums[::-1]:
            if n >= k:
                k = n
            elif n >= j:
                j = n
            else:
                return 1
        return 0

接下來是 942. DI String Match (easy)
https://leetcode.com/problems/di-string-match/

給一字串 s 。
如果 s[i] == 'I' 則 perm[i] < perm[i + 1],
如果 s[i] == 'D' 則 perm[i] > perm[i + 1]。
依據這個操作建立答案，數字範圍為0 ~ n

想法：

1. 遇到 "I" 下個數字一定要比較大，遇到 "D" 下個數字一定比較小。
2. 乾脆建立一個數列從0~n
3. 遇到 "I" 從左邊挖數字到ans，遇到 "D"從右邊抓數字到ans。如此一來，無論"I"、"D"怎麼排都可以排出答案。
   寫了兩種寫法，第一次真的去建立數列，第二次直接建立變數處理即可，因為數字是有序的。

class Solution:
    #必含有n+1個數字
    #將這些數字組成符合s的要求的搭配
    def diStringMatch(self, s: str) -> List[int]:
        numList = list(range(len(s)+1))
        ans = []
        for i in s:
            if i == "I":
                ans.append(numList.pop(0))
            else:
                ans.append(numList.pop())
        ans.append(numList.pop())
        return ans
    
    #簡化版本
    def diStringMatch(self, s: str) -> List[int]:
        L,R = 0,len(s)
        ans = []
        for i in s:
            if i =="I":
                ans.append(L)
                L+=1
            else:
                ans.append(R)
                R-=1
        return ans + [L]

接下來是 944. Delete Columns to Make Sorted (easy)
https://leetcode.com/problems/delete-columns-to-make-sorted/

給一文字串列 strs ，裡面含有多個文字，每個文字字母各數相同，當行列互調時，若要讓每一行都是字典排序，邀刪除幾行字？

簡單來說，就是行列對掉之後，進行sort，看跟原本一不一樣就可以找出答案。
以下也是兩種寫法，比較意外的是跑zip+sort居然會比雙重for迴圈快。

class Solution:
    #要刪除沒有按照字典排序的東西
    #直行橫列，要刪除的是"行"
    def minDeletionSize(self, strs: List[str]) -> int:
        ans = 0
        for i in range(len(strs[0])):
            for j in range(1,len(strs)):
                if strs[j][i] < strs[j-1][i]:
                    ans+=1
                    break
        return ans
    
    #這樣寫會比較快
    #未來只要有列轉行的寫法一律這樣寫
    def minDeletionSize(self, strs: List[str]) -> int:
        ans = 0
        for i in zip(*strs):
            if ''.join(sorted(i)) != ''.join(i):
                ans += 1
        return ans

以上為今天的練習，感謝大家