h*******e
发帖数: 1377 | 1 看了几个人的没发现太好的解法，自己的O(n) time const space又有点长46行 大家有
没有
好点的解法。 |
h*******e
发帖数: 1377 | 2 discuss 里面有一个， 但是感觉不大好。。
大家上代码的时候尽量 写点小思路，方便他人阅读~~ |
j*****8
发帖数: 3635 | 3 我的28行，不过看着也挺繁琐的。思路就是碰到递增的就一直加1，递减的话一直减，
碰到往上走时就回头check一下看那段递减的需不需要调整（负数，或者最小的不是1）
public int candy(int[] ratings) {
if(ratings == null || ratings.length == 0) return 0;
int len = ratings.length;
int[] num = new int[len];
for(int i = 0; i < len; i++) {
if(i == 0) num[i] = 1;
else {
if(ratings[i] > ratings[i-1]) num[i] = num[i-1] + 1;
else if(ratings[i] == ratings[i-1]) num[i] = 1;
else {
num[i] = num[i-1] > 1 ? 1 : num[i-1] - 1;
if(i == len - 1 || ratings[i] <= ratings[i+1])
if(num[i] != 1) adjust(ratings, num, i);
}
}
}
int result = 0;
for(int i = 0; i < len; i++) result += num[i];
return result;
}
private void adjust(int[] ratings, int[] num, int pos) {
int diff = 1 - num[pos];
while(pos >= 1 && ratings[pos] < ratings[pos-1]) {
num[pos] += diff;
pos--;
}
if(num[pos] <= num[pos+1]) num[pos] = num[pos+1] + 1;
} |
h*******e
发帖数: 1377 | 4 楼上做的挺好，只是多用了O(n) 的space, 我也得把我自己的算法帖一下，我的就是
check 上升下降的转折点，然后把 所有单调上升， 单调下降， 单调水平的部分拿出
来 把他们变成最小为一的上升或者下降序列 或者水平序列但是 单调性不变 用等差数
列求和 求部分和， 唯一tricky的地方就是 转折点需要取两边的单调序列的最大值~~~
one pass 不回头查的，空间时间复杂性都不错，但是就是代码太长了， 逻辑也不那
么清晰，还有没有时间空间复杂度类似的，但是思路或者代码比我这个好一些的。减到
了37行现在。
class Solution {
public:
int compare_int(int preVal, int val)
{ return preVal < val ? 1: (preVal > val? -1: 0); }
int candy(vector &ratings) {
int dirVal = 0, preDirVal = -2, preIndex = 0, curIndex, totSum = 0,
preEdge = 1;
for(int rateI = 1; rateI <= ratings.size(); ++ rateI)
{
int val, preVal = ratings[rateI-1];
if(rateI != ratings.size())
{
val = ratings[rateI];
dirVal = compare_int(preVal, val);
}
if(rateI == ratings.size() || preDirVal != -2 && preDirVal !=
dirVal )
{
curIndex = rateI -1;
int size = curIndex - preIndex + 1, newSum = 0;
int frontEdge, backEdge, inc;
if(preDirVal == 1)
{ frontEdge = 1; backEdge = size; inc = 1; }
else if(preDirVal == -1)
{ frontEdge = size; backEdge =1; inc = -1; }
else
{ frontEdge = backEdge = 1; inc = 0; }
totSum += frontEdge * size + size * (size -1 ) /2 * inc +
max(preEdge -frontEdge, 0)
- (rateI != ratings.size()? backEdge: 0);
preEdge = backEdge;
preIndex = curIndex;
}
preDirVal = dirVal;
}
return totSum;
}
}; |
w**********9
发帖数: 105 | 5 我这个解法也》30行，
int candy(vector &ratings) {
// Note: The Solution object is instantiated only once and is reused
by each test case.
int sum = ratings.size();
int r=0, l=0, nsum=0;
for (int i=1; i
if (ratings[i]>=ratings[i-1]) {
if (l<0) {
sum += -1*(nsum-l);
if (r+l<0) sum += -1*(r+l);
l=0;
nsum = 0;
r= (ratings[i]==ratings[i-1]) ? 0:1;
sum += r;
}
else {
if (ratings[i]>ratings[i-1]) ++r;
else r=0;
sum += r;
}
}
else {
--l;
nsum += l;
}
}
if (l<0) sum += -1*(nsum-l);
if (r+l<0) sum += -1*(r+l);
return sum;
} |
h*******e
发帖数: 1377 | 6 看起来不错能写个简单的思路么。
reused
【在 w**********9 的大作中提到】
: 我这个解法也》30行，
: int candy(vector &ratings) {
: // Note: The Solution object is instantiated only once and is reused
: by each test case.
: int sum = ratings.size();
: int r=0, l=0, nsum=0;
: for (int i=1; i: if (ratings[i]>=ratings[i-1]) {
: if (l<0) {
: sum += -1*(nsum-l);
|
j*****8
发帖数: 3635 | 7 嗯，是，那个O（n）的空间应该可以降到O(1)，没想这么多。。
~~
【在 h*******e 的大作中提到】
: 楼上做的挺好，只是多用了O(n) 的space, 我也得把我自己的算法帖一下，我的就是
: check 上升下降的转折点，然后把 所有单调上升， 单调下降， 单调水平的部分拿出
: 来 把他们变成最小为一的上升或者下降序列 或者水平序列但是 单调性不变 用等差数
: 列求和 求部分和， 唯一tricky的地方就是 转折点需要取两边的单调序列的最大值~~~
: one pass 不回头查的，空间时间复杂性都不错，但是就是代码太长了， 逻辑也不那
: 么清晰，还有没有时间空间复杂度类似的，但是思路或者代码比我这个好一些的。减到
: 了37行现在。
: class Solution {
: public:
: int compare_int(int preVal, int val)
|
w**********9
发帖数: 105 | 8 r 记录前一个连续上升的最高值，l记录连续下降值，负数，如果上升等与或高与下降
（r+l>=0) 就不比调整了。
【在 h*******e 的大作中提到】
: 看起来不错能写个简单的思路么。
:
: reused
|
h*******e
发帖数: 1377 | 9 这个似乎很巧妙阿， 好我再仔细看看你的代码。
【在 w**********9 的大作中提到】
: r 记录前一个连续上升的最高值，l记录连续下降值，负数，如果上升等与或高与下降
: （r+l>=0) 就不比调整了。
|
h*******e
发帖数: 1377 | 10 恩，你也看看warmspring99的算法么。
【在 j*****8 的大作中提到】
: 嗯，是，那个O（n）的空间应该可以降到O(1)，没想这么多。。
:
: ~~
|
|
|
x******u
发帖数: 17 | 11 public class Solution {
public int candy(int[] ratings) {
int num[] = new int[ratings.length];
for (int i = 0; i < ratings.length - 1; i++) {
if (ratings[i+1] > ratings[i]) num[i+1] = num[i] + 1;
}
for (int i = ratings.length - 1; i > 0; i--) {
if (ratings[i-1] > ratings[i]) num[i-1] = Math.max(num[i]+1, num
[i-1]);
}
int sum = 0;
for (int i = 0; i < num.length; i++)
sum += 1 + num[i];
return sum;
}
}
左边扫一遍，右边来一遍 |
j*****8
发帖数: 3635 | 12 有个小问题，为啥从零开始分配？题目要求不是至少得要有一个吗？
不过程序是AC了。
【在 h*******e 的大作中提到】
: 恩，你也看看warmspring99的算法么。
|
h*******e
发帖数: 1377 | 13 她是求增量，每个元素已经给赋了1了 在sum = ratings.size()的时候。。 再其他的
还没看太清楚~~还在看~~
------------
应该现在明白了
【在 j*****8 的大作中提到】
: 有个小问题，为啥从零开始分配？题目要求不是至少得要有一个吗？
: 不过程序是AC了。
|
l******e
发帖数: 54 | 14 20- 行 我的 right 是单调不回溯的 所以是 O(n) 时间，O(1) 空间也显然，程序也应
该显然
class Solution {
public:
int candy(vector& ratings) {
int sum = 0;
int left = -1, right = 1;
for (int i = 0; i < ratings.size(); ++i) {
if (i > 0 && ratings[i] <= ratings[i - 1]) {
left = i - 1;
}
right = max(right, i + 1);
while (right < ratings.size() && ratings[right] < ratings[right - 1]) {
++right;
}
sum += max(i - left, right - i);
}
return sum;
}
}; |
l******e
发帖数: 54 | 15 还是解释一下吧
left 表示从 i 开始向左最多能延伸到的点的边界，right 是向右
所以单调区间就是 (left, i] 和 [i, right) |
h*******e
发帖数: 1377 | 16 你的代码一向很好，我明天早上读一下子。
【在 l******e 的大作中提到】
: 20- 行 我的 right 是单调不回溯的 所以是 O(n) 时间，O(1) 空间也显然，程序也应
: 该显然
: class Solution {
: public:
: int candy(vector& ratings) {
: int sum = 0;
: int left = -1, right = 1;
: for (int i = 0; i < ratings.size(); ++i) {
: if (i > 0 && ratings[i] <= ratings[i - 1]) {
: left = i - 1;
|
j*****8
发帖数: 3635 | 17 en 那我就明白了。
班上还是有牛人阿，得多交流学习
【在 h*******e 的大作中提到】
: 她是求增量，每个元素已经给赋了1了 在sum = ratings.size()的时候。。 再其他的
: 还没看太清楚~~还在看~~
: ------------
: 应该现在明白了
|
w**********9
发帖数: 105 | 18 看着很简洁，我也好好学习一下。
【在 l******e 的大作中提到】
: 20- 行 我的 right 是单调不回溯的 所以是 O(n) 时间，O(1) 空间也显然，程序也应
: 该显然
: class Solution {
: public:
: int candy(vector& ratings) {
: int sum = 0;
: int left = -1, right = 1;
: for (int i = 0; i < ratings.size(); ++i) {
: if (i > 0 && ratings[i] <= ratings[i - 1]) {
: left = i - 1;
|
p********r
发帖数: 66 | 19 20 行
public int candySimple(int[] ratings){
if(ratings == null || ratings.length == 0) return 0;
if(ratings.length == 1) return 1;
int[] temp = new int[ratings.length];
temp[0] = 1;
for(int i = 1; i < ratings.length; i++){
if(ratings[i] > ratings[i-1])
temp[i] = temp[i-1] + 1;
else temp[i] = 1;
}
temp[ratings.length - 1] = Math.max(1, temp[ratings.length - 1]);
int last = 1, total = temp[ratings.length - 1];
for(int i = ratings.length - 2; i >= 0 ; i--){
if(ratings[i] > ratings[i+1])
last = last + 1;
else last = 1;
temp[i] = Math.max(temp[i], last);
total += temp[i];
}
return total;
} |
h*******e
发帖数: 1377 | 20 仔细读了，很赞阿！！ O(N)时间 O（1）空间。
【在 l******e 的大作中提到】
: 20- 行 我的 right 是单调不回溯的 所以是 O(n) 时间，O(1) 空间也显然，程序也应
: 该显然
: class Solution {
: public:
: int candy(vector& ratings) {
: int sum = 0;
: int left = -1, right = 1;
: for (int i = 0; i < ratings.size(); ++i) {
: if (i > 0 && ratings[i] <= ratings[i - 1]) {
: left = i - 1;
|
