diff options
author | Jack Sangdahl <jack@pngu.org> | 2024-08-18 17:38:10 -0600 |
---|---|---|
committer | Jack Sangdahl <jack@pngu.org> | 2024-08-18 17:38:10 -0600 |
commit | c7e6fe204a088a556f0022cbc56fbf5c6839749f (patch) | |
tree | c0e105ab8be2663a14fedae7848aece6ae53d85b /longest_valid_course.py | |
parent | 22c53848ffb964471e29d78ee4e879a81512fc71 (diff) | |
download | leetcode-c7e6fe204a088a556f0022cbc56fbf5c6839749f.tar.gz leetcode-c7e6fe204a088a556f0022cbc56fbf5c6839749f.zip |
1964. find the longest valid obstacle at each position
Diffstat (limited to 'longest_valid_course.py')
-rw-r--r-- | longest_valid_course.py | 40 |
1 files changed, 40 insertions, 0 deletions
diff --git a/longest_valid_course.py b/longest_valid_course.py new file mode 100644 index 0000000..985ca83 --- /dev/null +++ b/longest_valid_course.py @@ -0,0 +1,40 @@ +# 1964. Find the Longest Valid Obstacle Course at Each Position + +""" +you want to build obstacle courses. you are given a 0-indexed integer array +'obstacles' of length 'n' where 'obstacles[i]' describes the height of the +i'th obstacle. for every index 'i' between 0 and 'n - 1' (inclusive), find +the length of the longest obstacle course in 'obstacles' such that: +- you choose any number of obstacles between 0 and 'i' inclusive +- you must include the i'th obstacle in the course +- you must put the chosen obstacles in the same order as they appear in +'obstacles' +- every obstacle (except the first) is taller than or the same height as the +obstacle immediately before it return an array 'ans' of length 'n', where +'ans[i]' is the length of the longest obstacle course for index 'i' as +described above +""" + + +class Solution(object): + def longestObstacleCourseAtEachPosition(self, obstacles): + """ + :type obstacles: List[int] + :rtype: List[int] + """ + ans, stk = [], [] + for i in obstacles: + mid = bisect_right(stk, i) + if mid == len(stk): + stk.append(i) + else: + stk[mid] = i + ans.append(mid + 1) + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.longestObstacleCourseAtEachPosition(obstacles=[1, 2, 3, 2])) + print(obj.longestObstacleCourseAtEachPosition(obstacles=[2, 2, 1])) + print(obj.longestObstacleCourseAtEachPosition(obstacles=[3, 1, 5, 6, 4, 2])) |