503. Next Greater Element II

    xiaoxiao2021-03-25  59

    Given a circular array (the next element of the last element is the first element of the array), print the Next Greater Number for every element. The Next Greater Number of a number x is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn’t exist, output -1 for this number. 即对于每个元素输出它的离它最近的比它大的number,若不存在,输出-1,可循环搜索。

    language c:

    #include<stdlib.h> /** * Return an array of size *returnSize. * Note: The returned array must be malloced, assume caller calls free(). */ int* nextGreaterElements(int* nums, int numsSize, int* returnSize) { int i; *returnSize = numsSize; int* return_array = (int*)malloc(numsSize*sizeof(int)); int temp, j; bool iffind; for(i = 0; i< numsSize; i++) { temp = i; j = (i+1+numsSize)%numsSize; iffind = false; while(j != temp) { if (nums[j] > nums[i]) { return_array[i] = nums[j]; iffind = true; break; } j = (j+numsSize+1)%numsSize; } if (!iffind) return_array[i] = -1; } return return_array; }

    虽然能够成功通过,但是效率极低,耗时655ms。 去掉头文件的引用之后,变为了652ms

    然后在网上搜了一下,看见说可以用栈实现的,对数组遍历两次就好,先记在这里,以后有时间再过来实现。

    转载请注明原文地址: https://ju.6miu.com/read-39401.html

    最新回复(0)