โปรแกรมค้นหาจำนวนรายการย่อยที่มีสูงสุดและต่ำสุดหลังจากลบองค์ประกอบเดียวในPython

สมมติว่าเรามีรายการตัวเลขที่เรียกว่า nums และเราสามารถลบองค์ประกอบในรายการได้ไม่เกินหนึ่งรายการ เราต้องหาจำนวนสูงสุดของรายการย่อยที่มีทั้งค่าสูงสุดและต่ำสุดของรายการผลลัพธ์

ดังนั้น หากอินพุตเท่ากับ nums =[3, 2, 6, 2, 4, 10] ผลลัพธ์จะเป็น 8 ราวกับว่าเราลบ 10 เราจะได้ [3, 2, 6, 2, 4] และ มีแปดรายการย่อยที่มีทั้งค่าสูงสุดและต่ำสุด -

• [2, 6]

• [6, 2]

• [2, 6, 2]

• [3, 2, 6]

• [6, 2, 4]

• [2, 6, 2, 4]

• [3, 2, 6, 2]

• [3, 2, 6, 2, 4].

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชัน check() นี่จะใช้เวลา lst

• mn :=ต่ำสุดของ lst, mx :=สูงสุดของ lst

• min_pos :=null, max_pos :=null

• ยกเลิก :=0

• สำหรับแต่ละดัชนี i และค่า num ใน lst ให้ทำ

  • ถ้า num เท่ากับ mn แล้ว

    • min_pos :=ฉัน

  • ถ้า num เท่ากับ mx แล้ว

    • max_pos :=ผม

  • ถ้า min_pos เป็นโมฆะหรือ max_pos เป็นโมฆะ

    • ไปทำซ้ำต่อไป

  • ret :=ret + ขั้นต่ำของ min_pos และ (max_pos + 1)

• รีเทิร์น

• จากวิธีหลักให้ทำดังต่อไปนี้ -

• ถ้าขนาดของ nums <=1 แล้ว

  • ขนาดส่งคืนของ nums

• ret :=ตรวจสอบ (nums)

• สำหรับแต่ละ rem_cand ใน [minimum of nums , maximum of nums ] ทำ

  • ถ้าเกิด rem_cand เป็น 1 แล้ว

    • idx :=ดัชนีของ rem_cand เป็น nums

    • ret :=สูงสุดของ ret และตรวจสอบ (nums[from index 0 to idx - 1] concatenate nums[from index idx + 1 to end]

• รีเทิร์น

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

class Solution:
   def solve(self, nums):
      if len(nums) <= 1:
         return len(nums)
      def check(lst):
         mn, mx = min(lst), max(lst)
         min_pos, max_pos = None, None
         ret = 0
         for i, num in enumerate(lst):
            if num == mn:
               min_pos = i
            if num == mx:
               max_pos = i
            if min_pos is None or max_pos is None:
               continue
            ret += min(min_pos, max_pos) + 1
         return ret
      ret = check(nums)
      for rem_cand in [min(nums), max(nums)]:
         if nums.count(rem_cand) == 1:
            idx = nums.index(rem_cand)
            ret = max(ret, check(nums[:idx] + nums[idx + 1 :]))
      return ret
ob = Solution()
nums = [3, 2, 6, 2, 4, 10]
print(ob.solve(nums))

อินพุต

[3, 2, 6, 2, 4, 10]

ผลลัพธ์

8