※ 引述《cateran (雲川閒步)》之銘言：
: ※ 引述《suhang (suhang)》之銘言：
: : 我以前並沒有競賽經驗
: : 為了工作面試而開始寫leetcode, 最早連recursion都寫得很痛苦
: : 一邊練習也一邊跳槽，持續練習準備下次跳槽
: : 也寫了600+題了，很多題都反覆練習，每天下班持續練習個五題十題
: : 我自覺常用(考)的dfs, bfs, sort, tree, stack, queue
: : binary search, trie, binary search tree
: : 都算熟悉，都能很快寫出模板並了解為什麼，但似乎就卡在這
: : 好像就只會寫模板題，常常稍有變化就卡住了
: : (高手們的"基本結構/算法"一定包含更廣)
: : 例如 https://leetcode.com/problems/ternary-expression-parser/
: : 看了題我就直覺可以用 stack
: : 因此我就從i=0 開始往後走，開始分析遇到 ? or : 該怎麼入棧出棧
: : 但是越寫越雜，總是過不了，
: : 瞄了別人的做法 (開心！的確也可以用 stack解)
: : 別人從最後往前走，條理分明，20行解決
: : 另外又一題，這個例子更糟，完全沒想法
: : https://leetcode.com/problems/max-chunks-to-make-sorted/
: : 看了解答才知道，主要精神是求區間最大值，有兩種主要做法
: : 1 排序，然後對比原輸入(類似greedy的概念)
: : 2 用兩個arr記錄位置i左邊最大的和右手邊最小的元素(有點類似dp的概念)
: : 看了也能懂，而且他們也沒用更難的結構或是算法
: : 但自己本身的狀況就是糟，因為完全沒有想法，
: : 連掙扎都不知道怎麼抖，如果是面試，真的是乾整場
: : 這些症頭該怎麼辦？我該怎麼更進一步？
: 看了一下第二題
: 你是看哪裡的解答啊？
: 排序？兩個arr?
https://tinyurl.com/y2292rfg
: 這題用一個整數 記錄目前掃過的最大值 另一個整數記答案
: 然後掃過一次，當就好啦O(n), constant memory
: 個人看到題目都會先想辦法估計複雜度
: 然後想辦法找到這個複雜度下的演算法
如果有些想法，我也會試著推算
或者從leetcode的數據規模猜一下n^2 是否可行之類的
看別人經驗說，如果套上你的算法之後超過1M的運算應該就是TLE
: 比如說這題
: 很明顯當你掃到a_i的時候 就可以從前面的資料推論
: 是否從a_0到a_i可以當成一堆
: 如果不行就繼續掃下去
正如你所提到的這個方法以及原文中的版友推文
要能夠抽象化一個問題，然後再去思索適合的算法或是結構去執行
我想此題的抽象化結果就是:
找區間最大，當前區間最大不可和下個區間重疊，所以每個區間排列之後可以直接合併
所以discussion裡面
有人從左邊掃一遍右邊掃一遍
有人用monotoic stack
有人把輸入排個序，對比一下原輸入
但我滿常碰到某些題目，卻沒有丁點想法該如何抽象化該題
我會試著將題目暴力寫一遍，再去想想這個暴力是在“找”什麼東西
但仍會碰到某些題目無從下手
也許是某些知識點不足，或者是題意不夠明瞭，或是腦袋當機？
總覺得現在碰到一個瓶頸
又例如這題，https://leetcode.com/problems/sliding-window-maximum/
暴力法就是size k 的窗口反覆掃
最佳解是用一個單調棧，以前就是背下來
直到最近才有新的體悟
題目直白的說：要找窗口區間最大值
-> 在nums[i]左邊所有數中，哪個數字nums[j]比nums[i]大?
-> nums[j] 就成為上個區間的local max
-> 然後想辦法維護window size k這個要求
這類的問題似乎可以用單調棧去解
這題就跟上面的 https://leetcode.com/problems/max-chunks-to-make-sorted/ 很像
(在nums[i]左邊所有數中，哪個數字nums[j] 比nums[i]大?
那個數就成為這個區間的上界)
但我也不是立志成為算法高手
只是想過面試
: 如果可以就output++
: 然後往後掃描也不需要再回去看前面的資料
: 因此可以推論這是linear time可解的題目