※ 引述《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可解的题目