把每一輪的結果存到暫存buff，再回存nums當下做一輪的input。
int totalSteps(int* nums, int numsSize) {
int count=0;
int each_round=0;
int new_len = numsSize;
while (1)
{
each_round = 0;
int *stack=calloc (new_len, sizeof(int));
int idx = 0;
stack[0]=nums[0];
for (int i=0; i<new_len-1; i++)
{
if (nums[i+1]>= nums[i])
stack[++idx]=nums[i+1];
else
each_round++;
}
if (each_round == 0)
break;
new_len = idx+1;
memcpy(nums,stack,sizeof(int)*new_len);
// free(stack);
count++;
}
return count;
}
啊～會寫個正解嗎......
幾個重點兒～
1. 一輪要吃掉"右邊比左邊小"的全部, 即使吃別人的，在那一輪也會被比它大的吃掉
比方說 8,7,4,3,5 , 第一輪, 8吃掉7 , 7 吃掉4 , 4 吃掉3 ,這都是同一輪發生的事
（不存在有: 7被吃掉了那7 怎麼吃4 , 或是, 我怎麼知道這輪是8要吃掉7 , 還是7 要吃掉4 ，
答案是: 都吃！！！）
2. 因為 1的特性，所以大家都說要reverse 做 (到底為什麼你們知道！！！搖大家肩膀)
找到的比較看的懂的說法/推論是：因為從左往右看的話，以 1的例子來看，8吃掉7以後，就無法再跑7吃掉4了，因為7已經被吃掉了! 從stack 來想就是：8先進stack, 7來了發現7比8小，7就被pop掉了! (或是根本進不了stack)，而等到4進來的時候，4只看到8，4不會知道7的存在。
所以從右往左看的話，除了non-decreasing （不遞減, 可等於的遞增）變成decreasing (不能等於的遞減）之外，要被吃掉的人會在下一輪才被吃掉，就不會有該做的判斷沒做到。例如:
第一步 5先進stack，下一個3比5小, 3也進。接下來的4比3大，pop 3， 紀錄一個步數給4，表市4只pop掉一個，push 4。("pop掉幾個"先稱之為步數，見等下第三點！）
再來 7 看到4 , pop 4，一步；pop 5 ，也是一步，再來沒有了，要push7。7有兩步。
4本身帶的步數(目前是1)，五本身的步數是0。每次要pop的時候，取步數大的那個。也就是說!!!
第一洞：7(0+1)->4(1) 是取一步。(1>=1)
第二洞: 7(1+1=2) -> 5(0) 取兩步 (2>0)
push 7，取大步數存進7。（好像把第三點也講完了?)
最後8要吃掉7 是 2>1 所以答案是2步。
3. 第三點就是 每個item 要算步數，取大的。
當A push 進去時，要算步數- (1) 它pop掉幾個 (2) 要被pop的人"當初被push進去時的步數"
兩個取大的，再存進去A (被push進去的那個人)
初始值都是0，如果A沒有pop掉任何人就進stack了，它的步數就是0。
好了.....可以來看code了.....(倒) (這題花了我三天看懂別人解釋在講什麼，這不科學啊！)
注意: count ++的位置！放在max裡是有可能被加兩次的啊～（茶）
define max(A,B) (A>B)?(A):(B)
struct stack_item{
int val;
int steps;
};
int totalSteps(int* nums, int numsSize) {
struct stack_item *stack=calloc (numsSize, sizeof(struct stack_item));
int top = -1;
int max_count = 0;
for (int i=numsSize-1; i>=0; i--)
{
int count = 0;
while (top >=0 && nums[i]> stack[top].val)
{
count++;
count = max (stack[top].steps, count);
top--;
}
stack[++top].val = nums[i];
stack[top].steps = count;
if (max_count < count)
max_count = count;
}
return max_count;
}
先貼個別人的Orz
int totalSteps(int* nums, int numsSize) {
int* stack = (int*)malloc(numsSize * sizeof(int));
int* steps = (int*)calloc(numsSize, sizeof(int));
int top = -1;
int maxSteps = 0;
for (int i = 0; i < numsSize; i++) {
int currentStep = 0;
while (top >= 0 && nums[stack[top]] <= nums[i]) {
currentStep = currentStep > steps[stack[top]] ? currentStep : steps[stack[top]];
top--;
}
if (top >= 0) {
steps[i] = currentStep + 1;
maxSteps = maxSteps > steps[i] ? maxSteps : steps[i];
}
stack[++top] = i;
}
free(stack);
free(steps);
return maxSteps;
}
沒有留言:
張貼留言