diff options
Diffstat (limited to 'find_min_max_nodes_crit.c')
-rw-r--r-- | find_min_max_nodes_crit.c | 67 |
1 files changed, 67 insertions, 0 deletions
diff --git a/find_min_max_nodes_crit.c b/find_min_max_nodes_crit.c new file mode 100644 index 0000000..773eff9 --- /dev/null +++ b/find_min_max_nodes_crit.c @@ -0,0 +1,67 @@ +// 2058. Find the Minimum and Maximum Number of Nodes Between Critical Points +#include "leetcode.h" + +/* + * a critical point in a linked list is defined as either a local maxima or a + * local minima. anode is a local maxima if the current node has a value + * strictly greater than the previous node and the next node. a node is a minima + * if the current node has a value strictly smaller than the previous node and + * the next node. note that a node can only be a local maxima/minima if there + * exists both a previous node and a next node. given a linked list 'head', + * return an array of length 2 container '[min_distance, max_distance]' where + * 'min_distance' is the minimum distance between any two distinct nodes and + * oppositely true for 'max_distance'. if there are fewer than two critical + * points, return '[-1, -1]' + */ + +struct ListNode { + int val; + struct ListNode *next; +}; + +/** + * Note: The returned array must be malloced, assume caller calls free(). + */ +int *nodesBetweenCriticalPoints(struct ListNode *head, int *returnSize) { + int first = INT_MAX, last = 0, prev_val = head->val, min_d = INT_MAX; + for (int i = 0; head->next; ++i) { + if (fmax(prev_val, head->next->val) < head->val || + fmin(prev_val, head->next->val)) { + if (last) + min_d = fmin(min_d, i - last); + first = fmin(first, i); + last = i; + } + prev_val = head->val; + head = head->next; + } + int *ans = (int *)malloc(2 * sizeof(int)); + if (min_d == INT_MAX) + ans[0] = -1, ans[1] = -1; + else + ans[0] = min_d, ans[1] = last - first; + return ans; +} + +struct ListNode *create_node(int val) { + struct ListNode *new = (struct ListNode *)malloc(sizeof(struct ListNode)); + new->val = val; + new->next = NULL; + return new; +} + +int main() { + int rs1; + struct ListNode *head = create_node(5); + head->next = create_node(3); + head->next->next = create_node(1); + head->next->next->next = create_node(2); + head->next->next->next->next = create_node(5); + head->next->next->next->next->next = create_node(1); + head->next->next->next->next->next->next = create_node(2); + int *ndcp1 = nodesBetweenCriticalPoints(head, &rs1); + for (int i = 0; i < rs1; i++) + printf("%d ", ndcp1[i]); // expect: 1 3 + printf("\n"); + free(ndcp1); +} |