标签: Greedy

评分 0, 满分 5 星
0 票

贪心,用栈维护,在看到Stack之前几乎无想法.. 栈中存放到当前位置为止的最优解,对于新到来的元素,如果其小于栈顶元素并且栈顶元素不是最后一次出现并且新元素未在栈中出现,就可以弹栈了,直至新元素可以加入或者判断出不需要不加入。

Comments Off on [LeetCode]Remove Duplicate Letters

评分 0, 满分 5 星
0 票

贪心,在判断有解的情况下从随便一个点出发,如果到当前位置不可行,就向出发点的反向位置扩展,直到可行。如果可行,就从当前位置扩展下去。时空复杂度分别为O(n),O(1)。

评分 0, 满分 5 星
0 票

一个很直观的贪心问题。给第一个孩子一个糖果,首先正向遍历,如果下一个孩子rating比当前孩子rating高,则下一个孩子的糖果数目比当前孩子多1,否则糖果数目置为1。这样处理一遍之后,保证了每个孩子和他左边的孩子相比,糖果数目都是合法(rating高的糖果多)且最小的,但是和右边的相比却未必合法。因此还需要反向扫一遍,把那些rating比右侧高糖果却不比右侧多的孩子的糖果数目置为右侧糖果数+1.