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

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 199.116.167.226 ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1559245256.A.DF8.html ※ 编辑: suhang (199.116.167.226), 05/31/2019 04:00:04 ※ 编辑: suhang (199.116.167.226), 05/31/2019 04:01:22 ※ 编辑: suhang (199.116.167.226), 05/31/2019 04:05:10